結果

問題 No.94 圏外です。(EASY)
ユーザー mazeppa1108
提出日時 2016-12-18 18:08:57
言語 Scala(Beta)
(3.6.2)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

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