Submission #1542094

---

Source Code Expand

import java.util.*

data class Point(val x: Int, val y: Int)

fun main(args: Array<String>) {
    val (x1, y1, x2, y2) = readLine()!!.split(' ').map(String::toInt)
    val swapY: (Int) -> Int = if (y1 > y2) {{99999999 - it}} else {{it}}
    var p1 = Point(x1, swapY(y1))
    var p2 = Point(x2, swapY(y2))
    if (p1.x > p2.x) { val t = p1; p1 = p2; p2 = t }
    val n = readLine()!!.toInt()
    val points = ArrayList<Point>()
    for (i in 1..n) {
        val (x, y) = readLine()!!.split(' ').map(String::toInt)
        val p = Point(x, swapY(y))
        if (p.x in p1.x..p2.x && p.y in p1.y..p2.y) points.add(p)
    }
    points.sortBy { it.x }
    val ansMap = TreeMap<Int, Int>()
    ansMap.put(p1.y - 1, 0)
    for (p in points) {
        val fc = ansMap.floorEntry(p.y).value + 1
        val cy = ansMap.ceilingKey(p.y)
        if (cy != null) ansMap.remove(cy)
        ansMap.put(p.y, fc)
    }
    val q = ansMap.lastEntry().value
    var res = 100.0 * (p2.x - p1.x + p2.y - p1.y)
    if (q > 0) {
        if (p1.x == p2.x || p1.y == p2.y)
            res += Math.PI * 10.0 - 20.0
        else
            res -= (20.0 - Math.PI * 5.0) * q
    }
    println("%.15f".format(res))
}

Submission Info

Judge Result