/* Warning! * This solution is incorrect! 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 #define MAXN (500) int L,x[MAXN],y[MAXN],dp[MAXN],car[MAXN]; double best; void area(int lix,int rix,double dx,int low) { double sum=car[lix]-car[rix]; double ex=x[rix]-x[lix]-L; double ly=y[lix]+(double)(y[lix+1]-y[lix])*dx/(x[lix+1]-x[lix]); double ry=y[rix]+(double)(y[rix-1]-y[rix])*(ex-dx)/(x[rix]-x[rix-1]); double lp=ly; if (ry-1 && y[low]=0;i--) { int ix=i+1; while (ix>-1 && y[ix]>y[i]) ix=dp[ix]; dp[i]=ix; car[i]=car[i+1]+(y[i]+y[i+1])*(x[i+1]-x[i]); } low=lix=rix=0; while (x[rix]-x[0]1e-10) dx=rly/dlry; if (low<=lix) { int run=lix+1; low=-1; while (run>-1 && run=x[rix-1]) area(lix,rix,0,low); //Left if (dx>=0 && dx<=ex && x[lix]+dx+L>=x[rix-1] && x[lix]+dx<=x[lix+1]) area(lix,rix,dx,low); //Middle if (x[rix]-x[lix+1]>=L) lix++; else { area(lix,rix,ex,low); // Right rix++; if (y[rix-1]