結果

問題 No.94 圏外です。(EASY)
ユーザー mazeppa1108mazeppa1108
提出日時 2016-12-18 18:08:57
言語 Scala(Beta)
(3.4.0)
結果
TLE  
実行時間 -
コード長 1,215 bytes
コンパイル時間 8,681 ms
コンパイル使用メモリ 259,984 KB
実行使用メモリ 88,560 KB
最終ジャッジ日時 2023-09-12 09:04:18
合計ジャッジ時間 25,755 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 930 ms
62,640 KB
testcase_01 AC 942 ms
62,648 KB
testcase_02 AC 948 ms
62,572 KB
testcase_03 AC 888 ms
61,756 KB
testcase_04 AC 1,012 ms
62,796 KB
testcase_05 AC 1,039 ms
63,160 KB
testcase_06 AC 1,104 ms
63,692 KB
testcase_07 AC 1,168 ms
63,408 KB
testcase_08 AC 1,166 ms
63,436 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder

object Main {
  def main(args: Array[String]): Unit = {
    val n = io.StdIn.readLine().toInt
    val xys = (for (i <- 1 to n) yield
      io.StdIn.readLine().split(' ').map(_.toInt)).toList
    val gs = genCommutativeGroup(xys)
    val ans = n match {
      case 0 => 1.0
      case _ => {
        Math.sqrt(gs.map(maxDistance).max) + 2.0
      }
    }
    println(ans)
  }

  def distance2(p1: Array[Int], p2: Array[Int]): Double =
    Math.pow(p1(0) - p2(0), 2) + Math.pow(p1(1) - p2(1), 2)


  def commutable(p1: Array[Int], p2: Array[Int]): Boolean = {
    distance2(p1, p2) <= 100
  }


  def commutableGroup(xys: List[Array[Int]] , p1: Array[Int]): List[Array[Int]] = {
    if(xys.isEmpty) Nil else {
      val g = xys.filter(p2 => commutable(p1, p2))
      val next = xys.diff(g)
      g ++ g.flatMap(commutableGroup(next, _))
    }
  }


  def genCommutativeGroup(ps: List[Array[Int]]): List[List[Array[Int]]] = {
    ps match {
      case h :: t => {
        val g = commutableGroup(ps, h)
        g :: genCommutativeGroup(t.diff(g))
      }
      case _ => Nil
    }
  }


  def maxDistance(g: List[Array[Int]]): Double = {
    (for (i <- g; j <- g) yield distance2(i, j)).max
  }


}
0