/* NWERC 2006 * Sample solution to Airport * By Mikael Goldmann * Based on conversations with, and ideas from, Per Austrin * */ /* 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 * */ import java.util.*; public class airport_mg { static Scanner in = new Scanner(System.in); static java.text.NumberFormat format = new java.text.DecimalFormat("0.000"); static final long INF = Long.MAX_VALUE; int L; // or can L be a double?? int N; long[] X,Y; double[] area; // area[i] is ingetral from X[0] to X[i] long[][] _minY; //miny[i][j] is smallest of y[i..j] //and INF if i0) new airport_mg(); } long minY(int i, int j) { if (i>j) return INF; if (i==j) return Y[i]; if (i<0) return minY(i+1,j); if (j>=N) return minY(i,j-1); return _minY[i][j]; } airport_mg() throws Exception { N=in.nextInt(); L=in.nextInt(); X = new long[N]; Y = new long[N]; area=new double[N]; _minY=new long[N][N]; boolean verticalCase=false; for (int i=0; i0 && X[i]==X[i-1]) verticalCase=true; Y[i] = in.nextInt(); area[i] = (i==0 ? 0.0 : area[i-1]+(X[i]-X[i-1])*(Y[i]+Y[i-1])*0.5); for (int j=i-1; j>=0; --j) _minY[j][i] = Math.min(Y[j],minY(j+1,i)); } if (verticalCase) { System.err.println("Vertical slope"); //return; } /* Basic idea: * Conider all i<=j and find answer when left end of landing strip * is in [X[i],X[i+1]] and right end is in [X[i],X[i+1]]. * * Find x0 so that x0 is in first interval and x0+L is in second * and the height is the same at x0 and x0+L (if this is not possible, * choose the x0 (that legal w.r.t intervals) that minimizes height * difference at x0 and x0+L. * * If at some point between x0 and x0+L the height is less than y0, * set y0 to the minimum height in [X[i+1],X[j]]. * * Compute area removed if we flatten to level y0 between x0 and x0+L. */ double minA = Double.MAX_VALUE; for (int i=0; i X[i+1] || x0 > X[j+1]-L) x0 = Math.min(X[i+1],X[j+1]-L); if (x0 < X[i] || x0+L < X[j] || x0 > X[i+1] || x0+L > X[j+1]) continue; double y0 = minY(i+1,j); if (dxi !=0) y0 = Math.min(y0, Y[i]+ki*(x0-X[i])); if (dxj !=0) y0 = Math.min(y0, Y[j]+kj*(x0+L-X[j])); // Finally, compute area between line Y=y0 from x0 to x0+L // Area has four parts: // 1) integral from x0 to X[i+1] // 2) + integral from X[i+1] to X[j] // 3) + integral from X[j] to x0+L // 4) - y0*L (since we dig to Y=y0 rather than to Y=0) double A1,A2,A3,A4; A1 = dxi==0 ? 0 : 0.5*(X[i+1]-x0)*(Y[i+1]+Y[i]+ki*(x0-X[i])); A2 = area[j]-area[i+1]; A3 = dxj==0 ? 0 : 0.5*(x0+L-X[j])*(2*Y[j]+kj*(x0+L-X[j])); A4 = -y0*L; minA = Math.min(minA, A1+A2+A3+A4); } System.out.println(format.format(minA)); } }