結果

問題 No.168 ものさし
コンテスト
ユーザー バカらっく
提出日時 2019-11-29 09:48:24
言語 Kotlin
(2.1.0)
結果
RE  
実行時間 -
コード長 2,282 bytes
コンパイル時間 19,339 ms
コンパイル使用メモリ 453,356 KB
実行使用メモリ 62,204 KB
最終ジャッジ日時 2024-11-20 21:17:01
合計ジャッジ時間 28,996 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 RE * 2
other AC * 2 RE * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:4:10: warning: parameter 'arr' is never used
fun main(arr:Array<String>) {
         ^

ソースコード

diff # 

import java.math.BigDecimal
import java.util.*

fun main(arr:Array<String>) {
    val pointCount = readLine()!!.toInt()
    var list = (1..pointCount).map {id -> readLine()!!.split(" ").map { it.toLong() }.let { Point(id, it[0].toDouble(), it[1].toDouble()) } }.toMutableList()
    list.forEach {
        it.distanceStart =  dist(it, list.first())
        it.distanceGoal = dist(it, list.last())
    }
    val startPoint = list.first()
    val goalPoint = list.last()

    list = list.filter { it.distanceGoal <= startPoint.distanceGoal && it.distanceStart <= goalPoint.distanceStart }.sortedBy { it.distanceStart }.toMutableList()
    val map = PriorityQueue<Point>(kotlin.Comparator { t, t2 -> t.distanceStart.compareTo(t2.distanceStart) })
    map.add(list.first())
    list.removeAt(0)

    for(p in list) {
        for(p2 in map) {
            val d = dist(p2, p)
            if(d <= p2.distanceStart) {
                p.distanceStart = p2.distanceStart
                break
            } else if(d < p.distanceStart) {
                p.distanceStart = d
            }
        }
        map.add(p)
    }
    println(goalPoint.distanceStart)
}

fun dist(p1:Point, p2:Point):Long {
    var dist = Math.pow(Math.abs(p1.x - p2.x), 2.toDouble()).toBigDecimal()
    dist += Math.pow(Math.abs(p1.y - p2.y), 2.toDouble()).toBigDecimal()
    var ret = bigSqrt(dist, 0.toBigDecimal(), dist)
    ret = (Math.ceil(ret.toDouble() / 10) * 10).toLong()
    return ret.toLong()
}

fun bigSqrt(num:BigDecimal, min:BigDecimal, max:BigDecimal):Long {
    val mid = (max+min)/2.toBigDecimal()
    if(max-min<= 2.toBigDecimal()) {
        val minl = min.toLong()
        val midl = mid.toLong()
        val maxl = max.toLong()
        if(minl * minl >= num.toLong()) {
            return minl
        }
        if(midl * midl >= num.toLong()) {
            return midl
        }
        if(maxl * maxl >= num.toLong()) {
            return maxl
        }
        return  maxl + 1
    }
    var newMin = min;
    var newMax = max
    if(mid * mid > num) {
        newMax = mid + 1.toBigDecimal()
    } else {
        newMin = mid
    }
    return bigSqrt(num, newMin, newMax)
}
class Point(val id:Int, val x:Double, val y:Double) {
    var distanceStart: Long = 0
    var distanceGoal:Long = 0
}
0