/** * Find the allowed fences. Then use dynamic programming to find * the minimum cost triangulation of each subpolygon consisting * of the original polygon with a chord added and vertices on one * side of the chord excluded. Then for each such polyon additionally * compute a minimum cost triangulation where there is a triangle * with an edge on that chord and having one of the brothers inside * that triangle. Finally, try each triple of vertices for the * messenger's land and use the pre-computed minimum cost triangulations * to find the optimal solution. * * @author Finn Lidbetter */ val INF = Double.POSITIVE_INFINITY 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) { DoubleArray(n) { INF } } for (i in 0..n-1) { for (j in 0..n-1) { solve(i, j, fenceAllowed, cost, minCostTriangulation) } } // brotherTriangulation[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 vertices not between i and j in clockwise order, and exactly // one of the brothers is in the sub-polygon and in a triangle with an // edge from i to j. var brotherTriangulation = Array(n) { DoubleArray(n) { INF } } for (i in 0..n-1) { for (j in 0..n-1) { val side1 = sign(lines[i][j].cross(brother1)) val side2 = sign(lines[i][j].cross(brother2)) if (!fenceAllowed[i][j] || side1 == side2) { brotherTriangulation[i][j] = INF continue } var best = INF for (k in j+1..j+1+n-2) { val k0 = k % n if (k0 == i) { break } if (!fenceAllowed[i][k0] || !fenceAllowed[j][k0]) { continue } if (side1 < 0) { if (!inTriangle(i,j,k0,brother1,lines)) { continue } } else { if (!inTriangle(i,j,k0,brother2,lines)) { continue } } val t1 = minCostTriangulation[k0][j] val t2 = minCostTriangulation[i][k0] if (t1 == INF || t2 == INF) { continue } val sum = t1 + t2 + cost[i][k0] + cost[k0][j] if (best == INF || sum < best) { best = sum } } brotherTriangulation[i][j] = best } } var best = INF for (i in 0..n-1) { for (j in i+1..n-1) { if (!fenceAllowed[i][j]) { continue } for (k in j+1..n-1) { if (!fenceAllowed[i][k] || !fenceAllowed[j][k]) { continue } val edgeCost = cost[i][j] + cost[j][k] + cost[k][i] best = updateBest(i, j, k, best, edgeCost, minCostTriangulation, brotherTriangulation) best = updateBest(k, i, j, best, edgeCost, minCostTriangulation, brotherTriangulation) best = updateBest(j, k, i, best, edgeCost, minCostTriangulation, brotherTriangulation) } } } if (best == INF) { println("IMPOSSIBLE") } else { println(best) } } fun updateBest(i: Int, j: Int, k: Int, best: Double, edgeCost: Double, minCostTriangulation: Array, brotherTriangulation: Array): Double { val t1 = brotherTriangulation[j][i] val t2 = brotherTriangulation[k][j] val t3 = minCostTriangulation[i][k] if (t1 != INF && t2 != INF && t3 != INF) { val sum = t1 + t2 + t3 + edgeCost if (sum < best) { return sum } } return best } 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 INF } 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] != INF) { return minCostTriangulation[i][j] } var best = INF for (k in 1..n-1) { val ptIndex = (j+k) % n if (ptIndex == i) { break } 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 == INF || t2 == INF) { continue } var sum = t1 + t2 + fenceCost[i][ptIndex] + fenceCost[j][ptIndex] if (best == INF || 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 { 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 } 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 } }