結果

問題 No.94 圏外です。(EASY)
ユーザー mazeppa1108mazeppa1108
提出日時 2016-12-18 18:08:57
言語 Scala(Beta)
(3.4.0)
結果
TLE  
実行時間 -
コード長 1,215 bytes
コンパイル時間 9,001 ms
コンパイル使用メモリ 268,900 KB
実行使用メモリ 95,992 KB
最終ジャッジ日時 2024-06-29 21:48:45
合計ジャッジ時間 25,474 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 898 ms
68,984 KB
testcase_01 AC 888 ms
65,480 KB
testcase_02 AC 902 ms
65,476 KB
testcase_03 AC 847 ms
64,192 KB
testcase_04 AC 982 ms
65,764 KB
testcase_05 AC 997 ms
65,892 KB
testcase_06 AC 1,051 ms
65,900 KB
testcase_07 AC 1,080 ms
66,184 KB
testcase_08 AC 1,110 ms
66,296 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