import sys
# from math import hypot, sqrt
from decimal import *
getcontext().prec = 100
EPS = getcontext().power(Decimal(10),-30)
def parse_testcases(io):
T = int(io.readline())
tc = []
for _ in range(T):
N = int(io.readline().strip())
V = []
for _ in range(N):
(m, q) = map(Decimal, io.readline().strip().split())
V.append((m, q))
tc.append((N, V))
return tc
def _hypot(a,b):
return (a*a+b*b).sqrt()
class Point:
def __init__(self, a=0., b=0.):
self.x = a
self.y = b
def __sub__(self, other):
return Point(self.x - other.x, self.y - other.y)
def __xor__(self, other):
return (self.x * other.y) - (self.y * other.x)
def __mul__(self, other):
return (self.x * other.x) + (self.y * other.y)
def __eq__(self, other):
return (self.x == other.x) and (self.y == other.y)
def __lt__(self, other):
if self.x != other.x:
return self.x < other.x
return self.y < other.y
def norm(self):
# return (self.x*self.x+self.y*self.y).sqrt()
return _hypot(self.x, self.y)
def __str__(self):
return f"({self.x}, {self.y})"
def ccw(o, a, b):
v = (a - o) ^ (b - o)
return v >= -EPS
def dist(p0, p1, p2):
return ((p2.x - p1.x) * (p1.y - p0.y) - (p1.x - p0.x) * (p2.y - p1.y)) / _hypot(p2.x - p1.x, p2.y - p1.y)
def get_area(a, b, c):
s = (a + b + c) / Decimal(2)
area = s * (s - a) * (s - b) * (s - c)
return Decimal(0) if (area <= 0.) else area.sqrt()
def convex_hull(points):
assert(len(points) > 2)
points = list(sorted(points))
hull = []
for _ in range(2):
start = len(hull)
for point in points:
while(len(hull) >= start + 2 and ccw(hull[-1], point, hull[-2])):
hull.pop()
hull.append(point)
hull.pop()
points = points[::-1]
return hull
def origin_in_polygon(v):
n = len(v)
if n < 3:
return False
for i in range(1, n-1):
ok = 0
d1 = dist(v[i + 1], v[0], v[i])
if abs(d1) < EPS:
continue
a1 = dist(Point(Decimal(0),Decimal(0)), v[0], v[i])
if((d1 > 0 and ((i == 1 and a1 > EPS) or (i != 1 and a1 > -EPS))) or (d1 < 0 and ((i == 1 and a1 < -EPS) or (i != 1 and a1 < EPS)))):
ok += 1
d2 = dist(v[0], v[i], v[i + 1])
if abs(d2) < EPS:
continue
a2 = dist(Point(Decimal(0), Decimal(0)), v[i], v[i + 1])
if((d2 > 0 and a2 > EPS) or (d2 < 0 and a2 < -EPS)):
ok += 1
d3 = dist(v[i], v[i + 1], v[0])
if abs(d3) < EPS:
continue
a3 = dist(Point(Decimal(0), Decimal(0)), v[i + 1], v[0])
if((d3 > 0 and ((i == n - 2 and a3 > EPS) or (i != n - 2 and a3 > -EPS))) or (d3 < 0 and ((i == n - 2 and a3 < -EPS) or (i != n - 2 and a3 < EPS)))):
ok += 1
if ok == 3:
return True
return False
def solve_testcase(t):
(_, l) = t
v = [Point(m / q, Decimal(-1) / q) for (m,q) in l]
v = convex_hull(v)
if not origin_in_polygon(v):
return float("inf")
p = []
for i in range(len(v)):
a_1, b_1 = v[i].x, v[i].y
a_2, b_2 = v[(i + 1) % len(v)].x, v[(i + 1) % len(v)].y
d = (a_1 * b_2) - (a_2 * b_1)
p.append( Point((b_1 - b_2) / d, (a_2 - a_1) / d) )
area = Decimal(0)
for i in range(len(p)):
a = p[i].norm()
b = p[(i + 1) % len(p)].norm()
c = (p[i] - p[(i + 1) % len(p)]).norm()
area += get_area(a, b, c)
return area
def solve(input, output):
for i, t in enumerate(parse_testcases(input)):
print("Case #%d:" % (i + 1), str(float(solve_testcase(t))), file=output)
if __name__ == "__main__":
solve(sys.stdin, sys.stdout)
aW1wb3J0IHN5cwojIGZyb20gbWF0aCBpbXBvcnQgaHlwb3QsIHNxcnQKZnJvbSBkZWNpbWFsIGltcG9ydCAqCgoKZ2V0Y29udGV4dCgpLnByZWMgPSAxMDAKCkVQUyA9IGdldGNvbnRleHQoKS5wb3dlcihEZWNpbWFsKDEwKSwtMzApCgpkZWYgcGFyc2VfdGVzdGNhc2VzKGlvKToKICAgIFQgPSBpbnQoaW8ucmVhZGxpbmUoKSkKICAgIHRjID0gW10KICAgIGZvciBfIGluIHJhbmdlKFQpOgogICAgICAgIE4gPSBpbnQoaW8ucmVhZGxpbmUoKS5zdHJpcCgpKQogICAgICAgIFYgPSBbXQogICAgICAgIGZvciBfIGluIHJhbmdlKE4pOgogICAgICAgICAgICAobSwgcSkgPSBtYXAoRGVjaW1hbCwgaW8ucmVhZGxpbmUoKS5zdHJpcCgpLnNwbGl0KCkpCiAgICAgICAgICAgIFYuYXBwZW5kKChtLCBxKSkKICAgICAgICB0Yy5hcHBlbmQoKE4sIFYpKQogICAgcmV0dXJuIHRjCgpkZWYgX2h5cG90KGEsYik6CiAgICByZXR1cm4gKGEqYStiKmIpLnNxcnQoKQoKY2xhc3MgUG9pbnQ6CiAgICBkZWYgX19pbml0X18oc2VsZiwgYT0wLiwgYj0wLik6CiAgICAgICAgc2VsZi54ID0gYQogICAgICAgIHNlbGYueSA9IGIKCiAgICBkZWYgX19zdWJfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgcmV0dXJuIFBvaW50KHNlbGYueCAtIG90aGVyLngsIHNlbGYueSAtIG90aGVyLnkpCgogICAgZGVmIF9feG9yX18oc2VsZiwgb3RoZXIpOgogICAgICAgIHJldHVybiAoc2VsZi54ICogb3RoZXIueSkgLSAoc2VsZi55ICogb3RoZXIueCkKCiAgICBkZWYgX19tdWxfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgcmV0dXJuIChzZWxmLnggKiBvdGhlci54KSArIChzZWxmLnkgKiBvdGhlci55KQoKICAgIGRlZiBfX2VxX18oc2VsZiwgb3RoZXIpOgogICAgICAgIHJldHVybiAoc2VsZi54ID09IG90aGVyLngpIGFuZCAoc2VsZi55ID09IG90aGVyLnkpCgogICAgZGVmIF9fbHRfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgaWYgc2VsZi54ICE9IG90aGVyLng6CiAgICAgICAgICAgIHJldHVybiBzZWxmLnggPCBvdGhlci54CiAgICAgICAgcmV0dXJuIHNlbGYueSA8IG90aGVyLnkKCiAgICBkZWYgbm9ybShzZWxmKToKICAgICAgICAjIHJldHVybiAoc2VsZi54KnNlbGYueCtzZWxmLnkqc2VsZi55KS5zcXJ0KCkKICAgICAgICByZXR1cm4gX2h5cG90KHNlbGYueCwgc2VsZi55KQoKICAgIGRlZiBfX3N0cl9fKHNlbGYpOgogICAgICAgIHJldHVybiBmIih7c2VsZi54fSwge3NlbGYueX0pIgoKZGVmIGNjdyhvLCBhLCBiKToKICAgIHYgPSAoYSAtIG8pIF4gKGIgLSBvKQogICAgcmV0dXJuIHYgPj0gLUVQUwoKZGVmIGRpc3QocDAsIHAxLCBwMik6CiAgICByZXR1cm4gKChwMi54IC0gcDEueCkgKiAocDEueSAtIHAwLnkpIC0gKHAxLnggLSBwMC54KSAqIChwMi55IC0gcDEueSkpIC8gX2h5cG90KHAyLnggLSBwMS54LCBwMi55IC0gcDEueSkKCmRlZiBnZXRfYXJlYShhLCBiLCBjKToKICAgIHMgPSAoYSArIGIgKyBjKSAvIERlY2ltYWwoMikKICAgIGFyZWEgPSBzICogKHMgLSBhKSAqIChzIC0gYikgKiAocyAtIGMpCiAgICByZXR1cm4gRGVjaW1hbCgwKSBpZiAoYXJlYSA8PSAwLikgZWxzZSBhcmVhLnNxcnQoKQoKZGVmIGNvbnZleF9odWxsKHBvaW50cyk6CiAgICBhc3NlcnQobGVuKHBvaW50cykgPiAyKQogICAgcG9pbnRzID0gbGlzdChzb3J0ZWQocG9pbnRzKSkKICAgIGh1bGwgPSBbXQogICAgZm9yIF8gaW4gcmFuZ2UoMik6CiAgICAgICAgc3RhcnQgPSBsZW4oaHVsbCkKICAgICAgICBmb3IgcG9pbnQgaW4gcG9pbnRzOgogICAgICAgICAgICB3aGlsZShsZW4oaHVsbCkgPj0gc3RhcnQgKyAyIGFuZCBjY3coaHVsbFstMV0sIHBvaW50LCBodWxsWy0yXSkpOgogICAgICAgICAgICAgICAgaHVsbC5wb3AoKQogICAgICAgICAgICBodWxsLmFwcGVuZChwb2ludCkKICAgICAgICBodWxsLnBvcCgpCiAgICAgICAgcG9pbnRzID0gcG9pbnRzWzo6LTFdCiAgICByZXR1cm4gaHVsbAoKZGVmIG9yaWdpbl9pbl9wb2x5Z29uKHYpOgogICAgbiA9IGxlbih2KQoKICAgIGlmIG4gPCAzOgogICAgICAgIHJldHVybiBGYWxzZQoKICAgIGZvciBpIGluIHJhbmdlKDEsIG4tMSk6CiAgICAgICAgb2sgPSAwCgogICAgICAgIGQxID0gZGlzdCh2W2kgKyAxXSwgdlswXSwgdltpXSkKICAgICAgICBpZiBhYnMoZDEpIDwgRVBTOgogICAgICAgICAgICBjb250aW51ZQoKICAgICAgICBhMSA9IGRpc3QoUG9pbnQoRGVjaW1hbCgwKSxEZWNpbWFsKDApKSwgdlswXSwgdltpXSkKICAgICAgICBpZigoZDEgPiAwIGFuZCAoKGkgPT0gMSBhbmQgYTEgPiBFUFMpIG9yIChpICE9IDEgYW5kIGExID4gLUVQUykpKSBvciAoZDEgPCAwIGFuZCAoKGkgPT0gMSBhbmQgYTEgPCAtRVBTKSBvciAoaSAhPSAxIGFuZCBhMSA8IEVQUykpKSk6CiAgICAgICAgICAgIG9rICs9IDEKCiAgICAgICAgZDIgPSBkaXN0KHZbMF0sIHZbaV0sIHZbaSArIDFdKQogICAgICAgIGlmIGFicyhkMikgPCBFUFM6CiAgICAgICAgICAgIGNvbnRpbnVlCiAgICAKICAgICAgICBhMiA9IGRpc3QoUG9pbnQoRGVjaW1hbCgwKSwgRGVjaW1hbCgwKSksIHZbaV0sIHZbaSArIDFdKQogICAgICAgIGlmKChkMiA+IDAgYW5kIGEyID4gRVBTKSBvciAoZDIgPCAwIGFuZCBhMiA8IC1FUFMpKToKICAgICAgICAgICAgb2sgKz0gMQoKICAgICAgICBkMyA9IGRpc3QodltpXSwgdltpICsgMV0sIHZbMF0pCiAgICAgICAgaWYgYWJzKGQzKSA8IEVQUzoKICAgICAgICAgICAgY29udGludWUKCiAgICAgICAgYTMgPSBkaXN0KFBvaW50KERlY2ltYWwoMCksIERlY2ltYWwoMCkpLCB2W2kgKyAxXSwgdlswXSkKICAgICAgICBpZigoZDMgPiAwIGFuZCAoKGkgPT0gbiAtIDIgYW5kIGEzID4gRVBTKSBvciAoaSAhPSBuIC0gMiBhbmQgYTMgPiAtRVBTKSkpIG9yIChkMyA8IDAgYW5kICgoaSA9PSBuIC0gMiBhbmQgYTMgPCAtRVBTKSBvciAoaSAhPSBuIC0gMiBhbmQgYTMgPCBFUFMpKSkpOgogICAgICAgICAgICBvayArPSAxCiAgICAKICAgICAgICBpZiBvayA9PSAzOgogICAgICAgICAgICByZXR1cm4gVHJ1ZQoKICAgIHJldHVybiBGYWxzZQoKCmRlZiBzb2x2ZV90ZXN0Y2FzZSh0KToKICAgIChfLCBsKSA9IHQKCiAgICB2ID0gW1BvaW50KG0gLyBxLCBEZWNpbWFsKC0xKSAvIHEpIGZvciAobSxxKSBpbiBsXQogICAgdiA9IGNvbnZleF9odWxsKHYpCgogICAgaWYgbm90IG9yaWdpbl9pbl9wb2x5Z29uKHYpOgogICAgICAgIHJldHVybiBmbG9hdCgiaW5mIikKCiAgICBwID0gW10KICAgIGZvciBpIGluIHJhbmdlKGxlbih2KSk6CiAgICAgICAgYV8xLCBiXzEgPSB2W2ldLngsIHZbaV0ueQogICAgICAgIGFfMiwgYl8yID0gdlsoaSArIDEpICUgbGVuKHYpXS54LCB2WyhpICsgMSkgJSBsZW4odildLnkKICAgICAgICBkID0gKGFfMSAqIGJfMikgLSAoYV8yICogYl8xKQogICAgICAgIHAuYXBwZW5kKCBQb2ludCgoYl8xIC0gYl8yKSAvIGQsIChhXzIgLSBhXzEpIC8gZCkgKQoKICAgIGFyZWEgPSBEZWNpbWFsKDApCiAgICBmb3IgaSBpbiByYW5nZShsZW4ocCkpOgogICAgICAgIGEgPSBwW2ldLm5vcm0oKQogICAgICAgIGIgPSBwWyhpICsgMSkgJSBsZW4ocCldLm5vcm0oKQogICAgICAgIGMgPSAocFtpXSAtIHBbKGkgKyAxKSAlIGxlbihwKV0pLm5vcm0oKQogICAgICAgIGFyZWEgKz0gZ2V0X2FyZWEoYSwgYiwgYykKCiAgICByZXR1cm4gYXJlYQoKZGVmIHNvbHZlKGlucHV0LCBvdXRwdXQpOgogICAgZm9yIGksIHQgaW4gZW51bWVyYXRlKHBhcnNlX3Rlc3RjYXNlcyhpbnB1dCkpOgogICAgICAgIHByaW50KCJDYXNlICMlZDoiICUgKGkgKyAxKSwgc3RyKGZsb2F0KHNvbHZlX3Rlc3RjYXNlKHQpKSksIGZpbGU9b3V0cHV0KQoKaWYgX19uYW1lX18gPT0gIl9fbWFpbl9fIjoKICAgIHNvbHZlKHN5cy5zdGRpbiwgc3lzLnN0ZG91dCkKCg==