#!/bin/env python3
EPS = 1e-10
import sys
from math import hypot, sqrt
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(float, io.readline().strip().split())
V.append((m, q))
tc.append((N, V))
return tc
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 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) / 2.0
area = s * (s - a) * (s - b) * (s - c)
return 0.0 if (area <= 0.) else sqrt(area)
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(0., 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(0., 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(0., 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, -1.0 / 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 = 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(solve_testcase(t)), file=output)
if __name__ == "__main__":
solve(sys.stdin, sys.stdout)
IyEvYmluL2VudiBweXRob24zCgpFUFMgPSAxZS0xMAoKaW1wb3J0IHN5cwpmcm9tIG1hdGggaW1wb3J0IGh5cG90LCBzcXJ0CgpkZWYgcGFyc2VfdGVzdGNhc2VzKGlvKToKICAgIFQgPSBpbnQoaW8ucmVhZGxpbmUoKSkKICAgIHRjID0gW10KICAgIGZvciBfIGluIHJhbmdlKFQpOgogICAgICAgIE4gPSBpbnQoaW8ucmVhZGxpbmUoKS5zdHJpcCgpKQogICAgICAgIFYgPSBbXQogICAgICAgIGZvciBfIGluIHJhbmdlKE4pOgogICAgICAgICAgICAobSwgcSkgPSBtYXAoZmxvYXQsIGlvLnJlYWRsaW5lKCkuc3RyaXAoKS5zcGxpdCgpKQogICAgICAgICAgICBWLmFwcGVuZCgobSwgcSkpCiAgICAgICAgdGMuYXBwZW5kKChOLCBWKSkKICAgIHJldHVybiB0YwoKY2xhc3MgUG9pbnQ6CiAgICBkZWYgX19pbml0X18oc2VsZiwgYT0wLiwgYj0wLik6CiAgICAgICAgc2VsZi54ID0gYQogICAgICAgIHNlbGYueSA9IGIKCiAgICBkZWYgX19zdWJfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgcmV0dXJuIFBvaW50KHNlbGYueCAtIG90aGVyLngsIHNlbGYueSAtIG90aGVyLnkpCgogICAgZGVmIF9feG9yX18oc2VsZiwgb3RoZXIpOgogICAgICAgIHJldHVybiAoc2VsZi54ICogb3RoZXIueSkgLSAoc2VsZi55ICogb3RoZXIueCkKCiAgICBkZWYgX19tdWxfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgcmV0dXJuIChzZWxmLnggKiBvdGhlci54KSArIChzZWxmLnkgKiBvdGhlci55KQoKICAgIGRlZiBfX2VxX18oc2VsZiwgb3RoZXIpOgogICAgICAgIHJldHVybiAoc2VsZi54ID09IG90aGVyLngpIGFuZCAoc2VsZi55ID09IG90aGVyLnkpCgogICAgZGVmIF9fbHRfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgaWYgc2VsZi54ICE9IG90aGVyLng6CiAgICAgICAgICAgIHJldHVybiBzZWxmLnggPCBvdGhlci54CiAgICAgICAgcmV0dXJuIHNlbGYueSA8IG90aGVyLnkKCiAgICBkZWYgbm9ybShzZWxmKToKICAgICAgICByZXR1cm4gaHlwb3Qoc2VsZi54LCBzZWxmLnkpCgogICAgZGVmIF9fc3RyX18oc2VsZik6CiAgICAgICAgcmV0dXJuIGYiKHtzZWxmLnh9LCB7c2VsZi55fSkiCgpkZWYgY2N3KG8sIGEsIGIpOgogICAgdiA9IChhIC0gbykgXiAoYiAtIG8pCiAgICByZXR1cm4gdiA+PSAtRVBTCgpkZWYgZGlzdChwMCwgcDEsIHAyKToKICAgIHJldHVybiAoKHAyLnggLSBwMS54KSAqIChwMS55IC0gcDAueSkgLSAocDEueCAtIHAwLngpICogKHAyLnkgLSBwMS55KSkgLyBoeXBvdChwMi54IC0gcDEueCwgcDIueSAtIHAxLnkpCgpkZWYgZ2V0X2FyZWEoYSwgYiwgYyk6CiAgICBzID0gKGEgKyBiICsgYykgLyAyLjAKICAgIGFyZWEgPSBzICogKHMgLSBhKSAqIChzIC0gYikgKiAocyAtIGMpCiAgICByZXR1cm4gMC4wIGlmIChhcmVhIDw9IDAuKSBlbHNlIHNxcnQoYXJlYSkKCmRlZiBjb252ZXhfaHVsbChwb2ludHMpOgogICAgYXNzZXJ0KGxlbihwb2ludHMpID4gMikKICAgIHBvaW50cyA9IGxpc3Qoc29ydGVkKHBvaW50cykpCiAgICBodWxsID0gW10KICAgIGZvciBfIGluIHJhbmdlKDIpOgogICAgICAgIHN0YXJ0ID0gbGVuKGh1bGwpCiAgICAgICAgZm9yIHBvaW50IGluIHBvaW50czoKICAgICAgICAgICAgd2hpbGUobGVuKGh1bGwpID49IHN0YXJ0ICsgMiBhbmQgY2N3KGh1bGxbLTFdLCBwb2ludCwgaHVsbFstMl0pKToKICAgICAgICAgICAgICAgIGh1bGwucG9wKCkKICAgICAgICAgICAgaHVsbC5hcHBlbmQocG9pbnQpCiAgICAgICAgaHVsbC5wb3AoKQogICAgICAgIHBvaW50cyA9IHBvaW50c1s6Oi0xXQogICAgcmV0dXJuIGh1bGwKCmRlZiBvcmlnaW5faW5fcG9seWdvbih2KToKICAgIG4gPSBsZW4odikKCiAgICBpZiBuIDwgMzoKICAgICAgICByZXR1cm4gRmFsc2UKCiAgICBmb3IgaSBpbiByYW5nZSgxLCBuLTEpOgogICAgICAgIG9rID0gMAoKICAgICAgICBkMSA9IGRpc3QodltpICsgMV0sIHZbMF0sIHZbaV0pCiAgICAgICAgaWYgYWJzKGQxKSA8IEVQUzoKICAgICAgICAgICAgY29udGludWUKCiAgICAgICAgYTEgPSBkaXN0KFBvaW50KDAuLCAwLiksIHZbMF0sIHZbaV0pCiAgICAgICAgaWYoKGQxID4gMCBhbmQgKChpID09IDEgYW5kIGExID4gRVBTKSBvciAoaSAhPSAxIGFuZCBhMSA+IC1FUFMpKSkgb3IgKGQxIDwgMCBhbmQgKChpID09IDEgYW5kIGExIDwgLUVQUykgb3IgKGkgIT0gMSBhbmQgYTEgPCBFUFMpKSkpOgogICAgICAgICAgICBvayArPSAxCgogICAgICAgIGQyID0gZGlzdCh2WzBdLCB2W2ldLCB2W2kgKyAxXSkKICAgICAgICBpZiBhYnMoZDIpIDwgRVBTOgogICAgICAgICAgICBjb250aW51ZQogICAgCiAgICAgICAgYTIgPSBkaXN0KFBvaW50KDAuLCAwLiksIHZbaV0sIHZbaSArIDFdKQogICAgICAgIGlmKChkMiA+IDAgYW5kIGEyID4gRVBTKSBvciAoZDIgPCAwIGFuZCBhMiA8IC1FUFMpKToKICAgICAgICAgICAgb2sgKz0gMQoKICAgICAgICBkMyA9IGRpc3QodltpXSwgdltpICsgMV0sIHZbMF0pCiAgICAgICAgaWYgYWJzKGQzKSA8IEVQUzoKICAgICAgICAgICAgY29udGludWUKCiAgICAgICAgYTMgPSBkaXN0KFBvaW50KDAuLCAwLiksIHZbaSArIDFdLCB2WzBdKQogICAgICAgIGlmKChkMyA+IDAgYW5kICgoaSA9PSBuIC0gMiBhbmQgYTMgPiBFUFMpIG9yIChpICE9IG4gLSAyIGFuZCBhMyA+IC1FUFMpKSkgb3IgKGQzIDwgMCBhbmQgKChpID09IG4gLSAyIGFuZCBhMyA8IC1FUFMpIG9yIChpICE9IG4gLSAyIGFuZCBhMyA8IEVQUykpKSk6CiAgICAgICAgICAgIG9rICs9IDEKICAgIAogICAgICAgIGlmIG9rID09IDM6CiAgICAgICAgICAgIHJldHVybiBUcnVlCgogICAgcmV0dXJuIEZhbHNlCgoKZGVmIHNvbHZlX3Rlc3RjYXNlKHQpOgogICAgKF8sIGwpID0gdAoKICAgIHYgPSBbUG9pbnQobSAvIHEsIC0xLjAgLyBxKSBmb3IgKG0scSkgaW4gbF0KICAgIHYgPSBjb252ZXhfaHVsbCh2KQoKICAgIGlmIG5vdCBvcmlnaW5faW5fcG9seWdvbih2KToKICAgICAgICByZXR1cm4gZmxvYXQoImluZiIpCgogICAgcCA9IFtdCiAgICBmb3IgaSBpbiByYW5nZShsZW4odikpOgogICAgICAgIGFfMSwgYl8xID0gdltpXS54LCB2W2ldLnkKICAgICAgICBhXzIsIGJfMiA9IHZbKGkgKyAxKSAlIGxlbih2KV0ueCwgdlsoaSArIDEpICUgbGVuKHYpXS55CiAgICAgICAgZCA9IChhXzEgKiBiXzIpIC0gKGFfMiAqIGJfMSkKICAgICAgICBwLmFwcGVuZCggUG9pbnQoKGJfMSAtIGJfMikgLyBkLCAoYV8yIC0gYV8xKSAvIGQpICkKCiAgICBhcmVhID0gMC4KICAgIGZvciBpIGluIHJhbmdlKGxlbihwKSk6CiAgICAgICAgYSA9IHBbaV0ubm9ybSgpCiAgICAgICAgYiA9IHBbKGkgKyAxKSAlIGxlbihwKV0ubm9ybSgpCiAgICAgICAgYyA9IChwW2ldIC0gcFsoaSArIDEpICUgbGVuKHApXSkubm9ybSgpCiAgICAgICAgYXJlYSArPSBnZXRfYXJlYShhLCBiLCBjKQoKICAgIHJldHVybiBhcmVhCgpkZWYgc29sdmUoaW5wdXQsIG91dHB1dCk6CiAgICBmb3IgaSwgdCBpbiBlbnVtZXJhdGUocGFyc2VfdGVzdGNhc2VzKGlucHV0KSk6CiAgICAgICAgcHJpbnQoIkNhc2UgIyVkOiIgJSAoaSArIDEpLCBzdHIoc29sdmVfdGVzdGNhc2UodCkpLCBmaWxlPW91dHB1dCkKCmlmIF9fbmFtZV9fID09ICJfX21haW5fXyI6CiAgICBzb2x2ZShzeXMuc3RkaW4sIHN5cy5zdGRvdXQp