import java.util.Scanner; public class Fences { private static class Point { double x, y; public Point() { this(0,0); } public Point(double x, double y) { this.x = x; this.y = y; } public String toString() { return "(" + x + "," + y + ")"; } } public static Point [] points; public static int npoints; public static double[][] table; // store C(i,s) values public static double[][] cost; // store distance values public static double [][] triWithP1; // d[i][j] optimal cost when using a triangle with base point[i]-point[j] containing p1 public static double [][] triWithP2; // same with p2 public static double dist(int i, int j) { double dx = points[i].x - points[j].x; double dy = points[i].y - points[j].y; return Math.sqrt(dx*dx+dy*dy); } public static void fillTable(int n) { table = new double[n][n+1]; for(int i=0; i 0); } public static double[][] minTriangleContainingP(Point p) // for each segment s containing two exterior vertices, find min cost of triangulization // with p in a triangle with s as a side { double [][] ans = new double[npoints][npoints]; for(int i=0; i 1 && costij < ans[i][j]) { // System.out.println(" setting " + i + "," + j + " to " + costij); ans[i][j] = ans[j][i] = costij; } if (k-j > 1 && costjk < ans[j][k]) { // System.out.println(" setting " + j + "," + k + " to " + costjk); ans[j][k] = ans[k][j] = costjk; } if (!(i==0 && k == npoints-1) && costki < ans[k][i]) { // System.out.println(" setting " + i + "," + k + " to " + costki); ans[k][i] = ans[i][k] = costki; } } } /* for(int i=0; i 1; double t = ((d.x-c.x)*(c.y-a.y)-(c.x-a.x)*(d.y-c.y))/den; if (t < 0.0) return 2.0; return t; } public static double calcCost(Point p1, Point p2, int i, int j, int k) { int s; Point pi = points[i]; Point pj = points[j]; Point pk = points[k]; double innerTriCost = cost[i][j] + cost[j][k] + cost[k][i]; double tij = calcIntersect(p1, p2, pi, pj); double tjk = calcIntersect(p1, p2, pj, pk); double tki = calcIntersect(p1, p2, pk, pi); // System.out.println("Intersection of " + p1 + "-" + p2 + "," + points[i] + "-" + points[j] + ": " + tij); // System.out.println("Intersection of " + p1 + "-" + p2 + "," + points[j] + "-" + points[k] + ": " + tjk); // System.out.println("Intersection of " + p1 + "-" + p2 + "," + points[k] + "-" + points[i] + ": " + tki); if (tij < tjk && tjk < tki) { s = i - k + 1; if(s < 0) s += npoints; return triWithP1[i][j] + triWithP2[j][k] + innerTriCost + table[k][s]; } else if (tij < tki && tki < tjk) { s = k - j + 1; if(s < 0) s += npoints; return triWithP1[i][j] + triWithP2[k][i] + innerTriCost + table[j][s]; } else if (tjk < tki && tki < tij) { s = j - i + 1; if(s < 0) s += npoints; return triWithP1[j][k] + triWithP2[k][i] + innerTriCost + table[i][s]; } else if (tjk < tij && tij < tki) { s = i - k + 1; if(s < 0) s += npoints; return triWithP1[j][k] + triWithP2[i][j] + innerTriCost + table[k][s]; } else if (tki < tij && tij < tjk) { s = k - j + 1; if(s < 0) s += npoints; return triWithP1[k][i] + triWithP2[i][j] + innerTriCost + table[j][s]; } else if (tki < tjk && tjk < tij) { s = j - i + 1; if(s < 0) s += npoints; return triWithP1[k][i] + triWithP2[j][k] + innerTriCost + table[i][s]; } else { System.out.println("Should never get here"); System.exit(-1); } return 0.0; } public static double solve(Point p1, Point p2) { triWithP1 = minTriangleContainingP(p1); triWithP2 = minTriangleContainingP(p2); int [] indices = new int[npoints]; double minCost = Double.MAX_VALUE; for(int i=0; i