/* [NWERC'06] Mountopia's airport by: Jan Kuipers */ using namespace std; #include #include #include int N,L; vector x,y; double area (double xx) { int i=0; while (x[i+1]=xx+L) { double y1 = y[i]+(xx-x[i])/(x[i+1]-x[i])*(y[i+1]-y[i]); double y2 = y[i]+(xx+L-x[i])/(x[i+1]-x[i])*(y[i+1]-y[i]); return L*fabs(y2-y1)/2; } double yy = y[i]+(xx-x[i])/(x[i+1]-x[i])*(y[i+1]-y[i]); double low = yy; double res = (x[i+1]-xx)*(y[i+1]+yy)/2; i++; while (x[i+1]> runs; while (runs--) { cin >> N >> L; x=y=vector(N); for (int i=0; i> x[i] >> y[i]; double res=1e9; for (int fr=0; fr L) continue; if (x[to+1]-x[fr] < L) continue; double lo = max(x[to]-L, x[fr]); double hi = min(x[to+1]-L, x[fr+1]); for (int go=0; go<100; go++) { double x1 = (2*lo+hi)/3; double x2 = (lo+2*hi)/3; double area1 = area(x1); double area2 = area(x2); if (area1 < area2) hi=x2; else lo=x1; } res