#include #include #include #include #include using namespace std; #define SOLUTION 1 #define LOCAL 0 #define DEBUG 0 #define eps 1e-1 #define NMAX 211111 #define XMAX 10000000 namespace GEOM { int Sign(double a, double b, double c, double x, double y) { double r = a*x + b*y + c; if (fabs(r) < eps) return 0; else if (r > 0) return 1; else return -1; } int Parallel(double a1, double b1, double a2, double b2) { return fabs(a2*b1 - a1*b2) < eps; } int InBetween(double a, double b, double c) { if (fabs(a-c) < eps || fabs(b-c) < eps || (a <= c && c <= b) || (b <= c && c <= a)) return 1; else return 0; } int Intersect(double a1, double b1, double c1, double x2a, double y2a, double x2b, double y2b, double *xi, double *yi) { double a2, b2, c2; a2 = y2a - y2b; b2 = x2b - x2a; c2 = x2a * y2b - x2b * y2a; if (Parallel(a1, b1, a2, b2)) return 0; else { *xi = (b2*c1-b1*c2) / (a2*b1-a1*b2); *yi = (c2*a1-c1*a2) / (a2*b1-a1*b2); return 1; } } } int x[NMAX], y[NMAX], N; void ReadInput() { if (LOCAL) { srand(12345); N = 100000; } else scanf("%d", &N); int dif = 0; for (int i = 0; i < N; i++) if (LOCAL) { x[i] = i; if (i == 0) y[i] = -99000; else y[i] = y[i - 1] + dif; if ((i % 100) == 0) dif++; } else scanf("%d %d", &x[i], &y[i]); if (!LOCAL) { int i = 0, j = N - 1, tmp; while (i < j) { tmp = x[i]; x[i] = x[j]; x[j] = tmp; tmp = y[i]; y[i] = y[j]; y[j] = tmp; i++; j--; } } } double xpoly[NMAX], ypoly[NMAX]; int pnext[NMAX], pprev[NMAX], np, pstart; void ClipPoly(double a, double b, double c) { int q = pstart; int s = GEOM::Sign(a, b, c, xpoly[q], ypoly[q]); if (DEBUG) fprintf(stderr, "[ClipPoly] a=%.3lf b=%.3lf c=%.3lf q=%d s=%d\n", a, b, c, q, s); while (1) { int qnext = pnext[q]; int snext = GEOM::Sign(a, b, c, xpoly[qnext], ypoly[qnext]); if (s < 0 && snext >= 0) break; q = qnext; s = snext; if (q == pstart) break; } if (s >= 0) return; int qnext = pnext[q]; int snext = GEOM::Sign(a, b, c, xpoly[qnext], ypoly[qnext]); if (snext < 0) { pstart = -1; return; } if (snext == 0) pstart = qnext; else { assert(GEOM::Intersect(a, b, c, xpoly[q], ypoly[q], xpoly[qnext], ypoly[qnext], &xpoly[np], &ypoly[np])); pstart = np++; pnext[pstart] = qnext; } for (q = pstart; 1; q = pnext[q]) { qnext = pnext[q]; snext = GEOM::Sign(a, b, c, xpoly[qnext], ypoly[qnext]); if (snext < 0) break; } s = GEOM::Sign(a, b, c, xpoly[q], ypoly[q]); if (s == 0) pnext[q] = pstart; else { assert(GEOM::Intersect(a, b, c, xpoly[q], ypoly[q], xpoly[qnext], ypoly[qnext], &xpoly[np], &ypoly[np])); pnext[q] = np++; pnext[pnext[q]] = pstart; } } double SolveN2() { np = 4; xpoly[0] = ypoly[0] = -XMAX; xpoly[1] = XMAX; ypoly[1] = -XMAX; xpoly[2] = XMAX; ypoly[2] = XMAX; xpoly[3] = -XMAX; ypoly[3] = XMAX; pnext[0] = 1; pnext[1] = 2; pnext[2] = 3; pnext[3] = 0; pstart = 0; for (int p = 0; p < N; p++) { double a = y[p] - y[(p + 1) % N]; double b = x[(p + 1) % N] - x[p]; double c = (long long) x[p] * (long long) y[(p + 1) % N] - (long long) x[(p + 1) % N] * (long long) y[p]; ClipPoly(a, b, c); if (pstart < 0) break; if (DEBUG) { fprintf(stderr, "p=%d/%d (%d,%d)-(%d,%d): ", p, N, x[p], y[p], x[(p + 1) % N], y[(p + 1) % N]); int q = pstart; while (1) { fprintf(stderr, "%d(%.4lf,%.4lf) ", q, xpoly[q], ypoly[q]); q = pnext[q]; if (q == pstart) break; } fprintf(stderr, "\n"); } } if (pstart < 0) return 0.0; double area = 0.0; int q = pstart; while (1) { int qnext = pnext[q]; area += (xpoly[q] + xpoly[qnext]) * (ypoly[qnext] - ypoly[q]); q = qnext; if (q == pstart) break; } return 0.5 * fabs(area); } void ClipPoly2(double a, double b, double c, int q) { assert(GEOM::Sign(a, b, c, xpoly[q], ypoly[q]) < 0); pstart = q; while (1) { if (GEOM::Sign(a, b, c, xpoly[q], ypoly[q]) >= 0) break; q = pnext[q]; if (q == pstart) break; } if (q == pstart) { pstart = -1; return; } assert(GEOM::Sign(a, b, c, xpoly[q], ypoly[q]) >= 0); if (GEOM::Sign(a, b, c, xpoly[q], ypoly[q]) > 0) { assert(GEOM::Intersect(a, b, c, xpoly[q], ypoly[q], xpoly[pprev[q]], ypoly[pprev[q]], &xpoly[np], &ypoly[np])); pnext[np] = q; pprev[np] = pprev[q]; pprev[q] = np; pnext[pprev[np]] = np; q = np; np++; } int qa = q; q = pstart; while (GEOM::Sign(a, b, c, xpoly[q], ypoly[q]) < 0) q = pprev[q]; if (GEOM::Sign(a, b, c, xpoly[q], ypoly[q]) > 0) { assert(GEOM::Intersect(a, b, c, xpoly[q], ypoly[q], xpoly[pnext[q]], ypoly[pnext[q]], &xpoly[np], &ypoly[np])); /*if (!GEOM::Intersect(a, b, c, xpoly[q], ypoly[q], xpoly[pnext[q]], ypoly[pnext[q]], &xpoly[np], &ypoly[np])) { fprintf(stderr, "sq=%d snextq=%d\n", GEOM::Sign(a, b, c, xpoly[q], ypoly[q]), GEOM::Sign(a, b, c, xpoly[pnext[q]], ypoly[pnext[q]])); exit(7); }*/ pprev[np] = q; pnext[np] = pnext[q]; pnext[q] = np; pprev[pnext[np]] = np; q = np; np++; } pnext[q] = qa; pprev[qa] = q; pstart = q; } vector> vu; double SolveNlogN() { vu.resize(N); for (int p = 0; p < N; p++) { vu[p].first = atan2(y[(p + 1) % N] - y[p], x[(p + 1) % N] - x[p]); vu[p].second = p; } sort(vu.begin(), vu.end()); np = 4; xpoly[0] = ypoly[0] = -XMAX; xpoly[1] = XMAX; ypoly[1] = -XMAX; xpoly[2] = XMAX; ypoly[2] = XMAX; xpoly[3] = -XMAX; ypoly[3] = XMAX; pnext[0] = 1; pnext[1] = 2; pnext[2] = 3; pnext[3] = 0; pprev[1] = 0; pprev[2] = 1; pprev[3] = 2; pprev[0] = 3; pstart = 0; for (int i = 0; i < N; i++) { int p = vu[i].second; double a = y[p] - y[(p + 1) % N]; double b = x[(p + 1) % N] - x[p]; double c = (long long) x[p] * (long long) y[(p + 1) % N] - (long long) x[(p + 1) % N] * (long long) y[p]; int q = pstart; int s = GEOM::Sign(a, b, c, xpoly[q], ypoly[q]); if (s >= 0) { while (1) { int qnext = pnext[q], qprev = pprev[q]; double vprev = a * xpoly[qprev] + b * ypoly[qprev]; double vnext = a * xpoly[qnext] + b * ypoly[qnext]; double vq = a * xpoly[q] + b * ypoly[q]; //fprintf(stderr, " q=%d qprev=%d qnext=%d: vq=%.9lf vprev=%.9lf vnext=%.9lf\n", q, qprev, qnext, vq, vprev, vnext); if (vq < vprev + eps && vq < vnext + eps) break; q = pnext[q]; s = GEOM::Sign(a, b, c, xpoly[q], ypoly[q]); if (q == pstart) break; } } if (DEBUG) fprintf(stderr, "i=%d/%d (%.9lf): p=%d q=%d(%.3lf,%.3lf) s=%d\n", i, N, vu[i].first, p, q, xpoly[q], ypoly[q], s); if (s >= 0) continue; ClipPoly2(a, b, c, q); if (pstart < 0) break; if (DEBUG) { fprintf(stderr, "p=%d/%d (%d,%d)-(%d,%d): ", p, N, x[p], y[p], x[(p + 1) % N], y[(p + 1) % N]); int q = pstart; while (1) { fprintf(stderr, "%d(%.4lf,%.4lf) ", q, xpoly[q], ypoly[q]); q = pnext[q]; if (q == pstart) break; } fprintf(stderr, "\n"); } } if (pstart < 0) return 0.0; double area = 0.0; int q = pstart; while (1) { int qnext = pnext[q]; area += (xpoly[q] + xpoly[qnext]) * (ypoly[qnext] - ypoly[q]); q = qnext; if (q == pstart) break; } return 0.5 * fabs(area); } int main() { //freopen("allpoly_bad.in", "r", stdin); //freopen("all.out", "w", stdout); int T; if (LOCAL) T = 1; else scanf("%d", &T); while (T--) { ReadInput(); double area; if (SOLUTION == 0) area = SolveN2(); else area = SolveNlogN(); printf("%.20lf\n", area / 4e14); } return 0; }