/* Sample solution for NWERC'06: Mountopia's Airport * Author: Per Austrin * Algorithm: Use observation that mountain height at left point should be * as close as possible to height at right point, try all pairs * of segments for the left and right points. */ /* Warning! * This solution is incorrect (observation above is false)! It fails * for e.g. the following case: * * 4 8 * 0 0 * 4 2 * 7 2 * 12 7 * * The correct answer is 11.5. * * While this solution was one of the official judge solutions for * this problem, the official test data used does not contain any * cases such as the one above (so the test data used in the contest * was incomplete, but not incorrect). * * * / Per Austrin, Head Judge, NWERC 2006 * 2006-11-27 * */ #include #include using namespace std; int main(void) { int t; scanf("%d", &t); double ansX, ansY; while (t--) { int n, L, x[567], y[567]; scanf("%d%d", &n, &L); for (int i = 0; i < n; ++i) { scanf("%d%d", x+i, y+i); if (i > 0 && x[i] == x[i-1]) printf("bad case "); } double ans = 1e50; for (int i = 1; i < n; ++i) { double miny = 1e30, totA = 0; int dy1 = y[i]-y[i-1], dx1 = x[i]-x[i-1]; for (int j = i; j < n; miny r) continue; double t = l >? (disc ? (1.0*dx1*(dY*dx2+diff*dy2))/disc : l)