/* Note: Compile with inline expansion. */ /*------------------------------------------------------------------------*/ /* for VC 8+ */ #define _CRT_SECURE_NO_DEPRECATE #include #include #include #define INF (10000.0) /* a large number */ #define EPS (1e-12) #define NMAX (100) #define XMIN (-200) #define XMAX (+200) #ifndef solve #define solve solve_AC #endif #ifndef integ #define integ simps /* trape, simps, polyn */ #endif #ifndef fetch #define fetch getdic #endif static int n, dic[XMAX-XMIN+1]; static double r, vx[NMAX+2], vy[NMAX+2]; static double xmin, xmax; /*------------------------------------------------------------------------*/ void prepare(void) { int i, j = 0; for(i = XMIN; i <= XMAX; i++) { if(i >= (int)(vx[j+1])) { j++; } dic[i - XMIN] = j; } xmin = vx[1] - (r < 0 ? r : 0); xmax = vx[n] - (r > 0 ? r : 0); } /*------------------------------------------------------------------------*/ int getdic(double x) { return dic[(int)(floor((x) + EPS)) - XMIN]; } int binary(double x) { int i, j, m; i = 0; j = n + 2; while(j - i > 1) { m = (i + j) / 2; if(vx[m] - x > EPS) j = m; else i = m; } return i; } int linear(double x) { int i; for(i = 0; vx[i+1] - x <= EPS; i++) ; return i; } /*------------------------------------------------------------------------*/ double f(double x) { int i; i = fetch(x); return (vy[i+1] - vy[i]) * (x - vx[i]) / (vx[i+1] - vx[i]) + vy[i]; } double g(double x) { return f(x) * f(x + r); } /*------------------------------------------------------------------------*/ /* 台形則 */ double trape(double x0, double x1) { return (g(x1) + g(x0)) * (x1 - x0) / 2.0; } /* シンプソン則 */ double simps(double x0, double x1) { return (g(x1) + 4.0 * g((x1 + x0) / 2.0) + g(x0)) * (x1 - x0) / 6.0; } /* 通常の多項式積分 */ double polyn(double x0, double x1) { int i, j; double a0, b0, a1, b1, a, b, c, y0, y1; i = fetch(x0 + 0); j = fetch(x0 + r); a0 = (vy[i+1] - vy[i]) / (vx[i+1] - vx[i]); b0 = a0 * (0 - vx[i]) + vy[i]; a1 = (vy[j+1] - vy[j]) / (vx[j+1] - vx[j]); b1 = a1 * (r - vx[j]) + vy[j]; a = a0 * a1; b = a0 * b1 + a1 * b0; c = b0 * b1; y0 = a * x0 * x0 * x0 / 3.0 + b * x0 * x0 / 2.0 + c * x0; y1 = a * x1 * x1 * x1 / 3.0 + b * x1 * x1 / 2.0 + c * x1; return y1 - y0; } /*------------------------------------------------------------------------*/ double solve_AC(void) { double x[2*NMAX], w, S; int i, j; for(i = 0; i < n; i++) { x[i+0] = vx[i+1] - 0; x[i+n] = vx[i+1] - r; } for(i = 0; i < 2 * n; i++) { for(j = i + 1; j < 2 * n; j++) { if(x[i] > x[j]) { w = x[i]; x[i] = x[j]; x[j] = w; } } } S = 0.0; for(i = 1; i < 2 * n; i++) S += integ(x[i-1], x[i]); return S; } /*------------------------------------------------------------------------*/ #ifndef PHI1 #define PHI1 (4000000) #endif /* 固定数分割 */ double solve_WA1(void) { double S, h; int i; S = 0.0; h = (xmax - xmin) / PHI1; for(i = 0; i < PHI1; i++) S += integ(xmin + i * h, xmin + (i + 1) * h); return S; } /*------------------------------------------------------------------------*/ #ifndef PHI2 #define PHI2 (5e-5) #endif /* 固定幅分割 */ double solve_WA2(void) { double S; int i, m; S = 0.0; m = (int)(ceil((xmax - xmin) / PHI2)); for(i = 0; i < m; i++) S += integ(xmin + i * PHI2, xmin + (i + 1) * PHI2); return S; } /*------------------------------------------------------------------------*/ #ifndef PHI3 #define PHI3 (1e-6) #endif /* 幅を動的に決定 */ double solve_WA3(void) { double h, S1, S2; int i, m; h = xmax - xmin; m = 1; S1 = -1e+10; S2 = +1e+10; while(fabs(S1 - S2) > PHI3) { S1 = S2; S2 = 0.0; for(i = 0; i < m; i++) S2 += integ(xmin + i * h, xmin + (i + 1) * h); h /= 2; m *= 2; } return S2; } /*------------------------------------------------------------------------*/ #ifndef PHI4 #define PHI4 (1e-10) #endif double solve_WA4_sub(double, double); /* 適応型積分 */ double solve_WA4(void) { return solve_WA4_sub(xmin, xmax); } double solve_WA4_sub(double x0, double x1) { double xm, S1, S2; xm = (x0 + x1) / 2.0; S1 = integ(x0, x1); S2 = integ(x0, xm) + integ(xm, x1); if(fabs(S2 - S1) > PHI4) return solve_WA4_sub(x0, xm) + solve_WA4_sub(xm, x1); else return S2; } /*------------------------------------------------------------------------*/ int main(void) { int i; while(scanf("%d%lf", &n, &r), !(n == 0 && r == 0.0)) { vx[ 0 ] = -INF; vy[ 0 ] = 0; vx[n+1] = +INF; vy[n+1] = 0; for(i = 1; i <= n; i++) scanf("%lf%lf", &vx[i], &vy[i]); prepare(); printf("%.15g\n", solve()); } } /*------------------------------------------------------------------------*/