allpoly.py

from math import fabs

def ahead(x, y, z):
    x1 = (x[2] - y[2]) / (y[1] - x[1])
    x2 = (y[2] - z[2]) / (z[1] - y[1])

    cmpe = int(x1 > x2)

    return y[0] == cmpe

def areaL(x, y, z):
    x1 = (x[2] - y[2]) / (y[1] - x[1])
    x2 = (y[2] - z[2]) / (z[1] - y[1])

    return (y[2] * (x1 - x2))

test = int(raw_input())
for _ in xrange(test):
    n = int(raw_input())
    sq = (3 ** 0.5)
    inf = float('inf')

    x = [0.0 for _ in xrange(n)]
    y = [0.0 for _ in xrange(n)]

    for i in xrange(n):
        xt, yt = map(float, raw_input().split())

        x[i] = (xt - sq*yt) / 2
        y[i] = (sq*xt + yt) / 2

    v = []
    for i in xrange(n):
        m = (y[i] - y[i-1]) / (x[i] - x[i-1])
        c = y[i] - m*x[i]

        v.append((int(x[i] > x[i-1]), m, c))

    v.sort()
    idx = 0
    for i in xrange(n):
        maxC, minC = v[i][2], v[i][2]

        while i < n-1 and v[i][0] == v[i+1][0] and fabs(v[i][1] - v[i+1][1]) < 1e-10*v[i+1][1]:
            i += 1
            maxC = max(maxC, v[i][2])
            minC = min(minC, v[i][2])

        if v[i][0]:
            v[idx] = (v[i][0], v[i][1], minC)
        else:
            v[idx] = (v[i][0], v[i][1], maxC)
        idx += 1

    v = v[:idx]
    v.append(v[0])
    pol = [0, ]

    for i in xrange(2, idx+1):
        prev = i - 1
        while len(pol) >= 1 and not ahead(v[pol[-1]], v[prev], v[i]):
            prev = pol[-1]
            pol.pop()
        pol.append(prev)

    if len(pol) <= 2:
        print 0.0

    else:
        start, area = 0, 0.0

        while ahead(v[pol[start]], v[pol[-1]], v[pol[start + 1]]):
            start += 1

        for j in xrange(start, len(pol)-2):
            area += areaL(v[pol[j]], v[pol[j+1]], v[pol[j+2]])
        area += areaL(v[pol[-1]], v[pol[0]], v[pol[1]]);
        area += areaL(v[pol[-2]], v[pol[-1]], v[pol[0]]);

        print '%.10f' % (area / 8e14, )