import kotlin.math.PI import kotlin.math.atan /** * Create a convex hull, we only need to do the top part. The points with the greatest angles are right next to the * island boundaries, so we just have check 2 corners. */ fun main() { val points = System.`in`.bufferedReader().lineSequence().drop(1) .map { line -> line.split(" ", limit = 2).map { it.toInt() }.let { (x, y) -> x to y } }.toList() val start = points.first() val end = points.last() val (east, west) = points.monotoneChainConvexUpperHull() println( (atan(west.second.toDouble() / (west.first - start.first)) / (2 * PI) * 360) .coerceAtLeast(atan(east.second.toDouble() / (end.first.toDouble() - east.first)) / (2 * PI) * 360) ) } typealias Point = Pair fun cross(O: Point, A: Point, B: Point) = (A.first - O.first) * (B.second - O.second) - (A.second - O.second) * (B.first - O.first) fun List.monotoneChainConvexUpperHull(): Pair { if (size == 3) { return get(1) to get(1) } val hull = Array(2 * size) { -10000 to -10000 } var k = 2 // lower hull always have 2 points var i: Int = size - 1 val t = k + 1 while (i >= 0) { while (k >= t && cross(hull[k - 2], hull[k - 1], get(i)) <= 0) k-- hull[k++] = get(i) i-- } return hull[3] to hull[k - 2] }