/** * 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. * Try each triple of vertices for the messenger's land. Then check * which regions the brothers fall in and find a minimum cost triangulation * that has each brother in a triangle sharing an edge with the messenger's * land. * * This submission should get TLE because it does not precompute the minimum * cost triangulations where a brother is in a triangle with a specific edge. * Time complexity: O(n^4) * * @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 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 (b1index1, b1index2) = indexPair(i,j,k, lines, brother1) val (b2index1, b2index2) = indexPair(i,j,k, lines, brother2) if (b1index1 == -1 || b2index1 == -1) { continue } if (b1index1 == b2index1) { continue } var emptyIndex1 = i + j + k - (b1index1 + b2index1) var emptyIndex2 = i + j + k - (b1index2 + b2index2) val t1 = minCostTriangulation[emptyIndex2][emptyIndex1] if (t1 == null) { continue } var b1Best: Double? = null for (l in b1index1+1..b1index1+n-1) { val l0 = l%n if (l0==b1index2) { break } if (!fenceAllowed[b1index1][l0] || !fenceAllowed[b1index2][l0]) { continue } if (!inTriangle(b1index1, b1index2, l0, brother1, lines)) { continue } val b1t1 = minCostTriangulation[b1index2][l0] val b1t2 = minCostTriangulation[l0][b1index1] if (b1t1 == null || b1t2 == null) { continue } val b1sum = b1t1!! + b1t2!! + cost[l0][b1index1] + cost[l0][b1index2] if (b1Best == null || b1sum < b1Best) { b1Best = b1sum } } if (b1Best == null) { continue } var b2Best: Double? = null for (l in b2index1+1..b2index1+n-1) { val l0 = l%n if (l0==b2index2) { break } if (!fenceAllowed[b2index1][l0] || !fenceAllowed[b2index2][l0]) { continue } if (!inTriangle(b2index1, b2index2, l0, brother2, lines)) { continue } val b2t1 = minCostTriangulation[b2index2][l0] val b2t2 = minCostTriangulation[l0][b2index1] if (b2t1 == null || b2t2 == null) { continue } val b2sum = b2t1!! + b2t2!! + cost[l0][b2index1] + cost[l0][b2index2] if (b2Best == null || b2sum < b2Best) { b2Best = b2sum } } if (b2Best == null) { continue } val sum = t1!! + b1Best!! + b2Best!! + cost[i][j] + cost[j][k] + cost[k][i] if (best == null || sum < best) { best = sum } } } } if (best == null) { println("IMPOSSIBLE") } else { println(best!!) } } fun indexPair(i: Int, j: Int, k: Int, lines: Array>, p: Point): Pair { if (lines[i][j].cross(p) > 0L) { return Pair(i, j) } if (lines[j][k].cross(p) > 0L) { return Pair(j, k) } if (lines[k][i].cross(p) > 0L) { return Pair(k, i) } return Pair(-1, -1) } 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 } }