/** * This submission gets WRONG ANSWER because it incorrectly assumes that * the brothers' and messenger's lands must have at least one edge along * the boundary of the provided polygon. * * @author Finn Lidbetter */ fun main() { val n = readln().toInt() var pts = Array(n) { val (x, y) = readln().split(" ").map{ it.toLong() } Point(x, y) } val (bx1, by1) = readln().split(" ").map { it.toLong() } val (bx2, by2) = readln().split(" ").map { it.toLong() } val brother1 = Point(bx1, by1) val brother2 = Point(bx2, by2) val lines = Array(n) { i -> Array(n) { j -> Line(pts[i], pts[j]) } } val fenceAllowed = Array(n) { i -> BooleanArray(n) { j -> ( i != j && lines[i][j].cross(brother1) != 0L && lines[i][j].cross(brother2) != 0L ) } } val cost = Array(n) { i -> DoubleArray(n) { j -> ( if ((i+1) % n == j || ((j+1)% n ) == i) { 0.0 } else { lines[i][j].cost() } ) } } // minCostTriangulation[i][j] is the minimum cost to triangulate the // sub-polygon from vertex i to vertex j, where the sub-polygon consists // of only the points not between i and j in clockwise order. var minCostTriangulation = Array(n) { Array(n) { null } } for (i in 0..n-1) { for (j in 0..n-1) { solve(i, j, fenceAllowed, cost, minCostTriangulation) } } var best: Double? = null for (i in 0..n-1) { for (j in 0..n-1) { if (i == j || (j+1) % n == i) { continue } if (!fenceAllowed[i][j] || !fenceAllowed[i][(j+1)%n]) { continue } // Brother in triangle with corners at i, j, j+1. if (!(inTriangle(i, j, (j+1)%n, brother1, lines) xor inTriangle(i, j, (j+1)%n, brother2, lines))) { continue } // Case 1: // Messenger in i, j+1, j+2. // Other brother in i, j+2, j+3 val case1cost = computeCostCase1(i, j, brother1, brother2, lines, cost, minCostTriangulation, fenceAllowed) if (case1cost != null && (best == null || case1cost < best!!)) { best = case1cost } // Case 2: // Messenger in i, j+1, j+2 // Other brother in i, j+2, i-1 val case2cost = computeCostCase2(i, j, brother1, brother2, lines, cost, minCostTriangulation, fenceAllowed) if (case2cost != null && (best == null || case2cost < best!!)) { best = case2cost } } } if (best == null) { println("IMPOSSIBLE") } else { println(best!!) } } /** * Case 1: * Messenger in i, j+1, j+2. * Other brother in i, j+2, j+3 */ fun computeCostCase1( i: Int, j: Int, b1: Point, b2: Point, lines: Array>, cost: Array, triangulation: Array>, fenceAllowed: Array ): Double? { val n = lines.size val j1 = (j+1) % n val j2 = (j+2) % n val j3 = (j+3) % n if (i == j1 || i == j2 || i == j3) { return null } if (!fenceAllowed[i][j2] || !fenceAllowed[i][j3]) { return null } if (inTriangle(i, j1, j2, b1, lines) || inTriangle(i, j1, j2, b2, lines)) { return null } if (!inTriangle(i, j2, j3, b1, lines) && !inTriangle(i, j2, j3, b2, lines)) { return null } val t1 = triangulation[j][i]; val t2 = triangulation[i][j3]; if (t1 == null || t2 == null) { return null } return t1!! + t2!! + cost[i][j1] + cost[i][j2] + cost[j][i] + cost[i][j3] } /** * Case 2: * Messenger in i, j+1, j+2 * Other brother in i, j+2, i-1 */ fun computeCostCase2( i: Int, j: Int, b1: Point, b2: Point, lines: Array>, cost: Array, triangulation: Array>, fenceAllowed: Array ): Double? { val n = lines.size val j1 = (j+1) % n val j2 = (j+2) % n val i1 = (i-1+n) % n if (i == j1 || i == j2 || i1 == j2) { return null } if (!fenceAllowed[i][j2] || !fenceAllowed[i1][j2]) { return null } if (inTriangle(i, j1, j2, b1, lines) || inTriangle(i, j1, j2, b2, lines)) { return null } if (!inTriangle(i, j2, i1, b1, lines) && !inTriangle(i, j2, i1, b2, lines)) { return null } val t1 = triangulation[j][i]; val t2 = triangulation[i1][j2]; if (t1 == null || t2 == null) { return null } return t1!! + t2!! + cost[i][j1] + cost[i][j2] + cost[j][i] + cost[i1][j2] } fun inTriangle(a: Int, b: Int, c: Int, p: Point, lines: Array>): Boolean { val line1 = lines[a][b] val line2 = lines[b][c] val line3 = lines[c][a] val side1 = sign(line1.cross(p)) var side2 = sign(line2.cross(p)) var side3 = sign(line3.cross(p)) return side1 * side2 > 0 && side1 * side3 > 0 } /** * Return -1 if the input is negative, 1 if the input is positive, 0 otherwise. */ fun sign(a: Long): Long { if (a > 0) { return 1L } if (a < 0) { return -1L } return 0L } fun solve( i: Int, j: Int, fenceAllowed: Array, fenceCost: Array, minCostTriangulation: Array> ): Double? { if (i == j) { return null } val n = fenceAllowed.size if ((j+2) % n == i || (j+1) % n == i) { minCostTriangulation[i][j] = 0.0 return 0.0 } if (minCostTriangulation[i][j] != null) { return minCostTriangulation[i][j] } var best: Double? = null for (k in 1..n-1) { if ((j+k)%n == i) { break } val ptIndex = (j+k) % n if (fenceAllowed[j][ptIndex] && fenceAllowed[i][ptIndex]) { val t1 = solve(i, ptIndex, fenceAllowed, fenceCost, minCostTriangulation) val t2 = solve(ptIndex, j, fenceAllowed, fenceCost, minCostTriangulation) if (t1 == null || t2 == null) { continue } var sum = t1!! + t2!! + fenceCost[i][ptIndex] + fenceCost[j][ptIndex] if (best == null || sum < best) { best = sum } } } minCostTriangulation[i][j] = best return best } class Point(val x: Long, val y: Long) class Line(val p1: Point, val p2: Point) { fun cost(): Double { //fun cost(): Long { val dx = p2.x - p1.x val dy = p2.y - p1.y val distSq = dx * dx + dy * dy var dist = kotlin.math.sqrt(distSq.toDouble()) return dist /* var dist = kotlin.math.sqrt(distSq.toDouble()).toLong() while (dist > 0 && dist * dist >= distSq) { dist -= 1 } while (dist * dist < distSq) { dist += 1 } return dist */ } fun cross(p: Point): Long { val x1 = p2.x - p1.x val y1 = p2.y - p1.y val x2 = p.x - p1.x val y2 = p.y - p1.y return x1 * y2 - y1 * x2 } fun midIntersects(l2: Line): Boolean { val l2opposites = (cross(l2.p1) * cross(l2.p2)) < 0 val thisOpposites = (l2.cross(p1) * l2.cross(p2)) < 0 return l2opposites && thisOpposites } fun hasPoint(p: Point): Boolean { if (cross(p) != 0L) { return false } if (p1.x < p2.x) { return p1.x <= p.x && p.x <= p2.x } else if (p2.x < p1.x) { return p2.x <= p.x && p.x <= p1.x } else if (p1.y < p2.y) { return p1.y <= p.y && p.y <= p2.y } return p2.y <= p.y && p.y <= p1.y } }