fork(1) download
copy 
  1. #!/bin/env python3
  2.  
  3. EPS = 1e-10
  4.  
  5. import sys
  6. from math import hypot, sqrt
  7.  
  8. def parse_testcases(io):
  9.     T = int(io.readline())
  10.     tc = []
  11.     for _ in range(T):
  12.         N = int(io.readline().strip())
  13.         V = []
  14.         for _ in range(N):
  15.             (m, q) = map(float, io.readline().strip().split())
  16.             V.append((m, q))
  17.         tc.append((N, V))
  18.     return tc
  19.  
  20. class Point:
  21.     def __init__(self, a=0., b=0.):
  22.         self.x = a
  23.         self.y = b
  24.  
  25.     def __sub__(self, other):
  26.         return Point(self.x - other.x, self.y - other.y)
  27.  
  28.     def __xor__(self, other):
  29.         return (self.x * other.y) - (self.y * other.x)
  30.  
  31.     def __mul__(self, other):
  32.         return (self.x * other.x) + (self.y * other.y)
  33.  
  34.     def __eq__(self, other):
  35.         return (self.x == other.x) and (self.y == other.y)
  36.  
  37.     def __lt__(self, other):
  38.         if self.x != other.x:
  39.             return self.x < other.x
  40.         return self.y < other.y
  41.  
  42.     def norm(self):
  43.         return hypot(self.x, self.y)
  44.  
  45.     def __str__(self):
  46.         return f"({self.x}, {self.y})"
  47.  
  48. def ccw(o, a, b):
  49.     v = (a - o) ^ (b - o)
  50.     return v >= -EPS
  51.  
  52. def dist(p0, p1, p2):
  53.     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)
  54.  
  55. def get_area(a, b, c):
  56.     s = (a + b + c) / 2.0
  57.     area = s * (s - a) * (s - b) * (s - c)
  58.     return 0.0 if (area <= 0.) else sqrt(area)
  59.  
  60. def convex_hull(points):
  61.     assert(len(points) > 2)
  62.     points = list(sorted(points))
  63.     hull = []
  64.     for _ in range(2):
  65.         start = len(hull)
  66.         for point in points:
  67.             while(len(hull) >= start + 2 and ccw(hull[-1], point, hull[-2])):
  68.                 hull.pop()
  69.             hull.append(point)
  70.         hull.pop()
  71.         points = points[::-1]
  72.     return hull
  73.  
  74. def origin_in_polygon(v):
  75.     n = len(v)
  76.  
  77.     if n < 3:
  78.         return False
  79.  
  80.     for i in range(1, n-1):
  81.         ok = 0
  82.  
  83.         d1 = dist(v[i + 1], v[0], v[i])
  84.         if abs(d1) < EPS:
  85.             continue
  86.  
  87.         a1 = dist(Point(0., 0.), v[0], v[i])
  88.         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)))):
  89.             ok += 1
  90.  
  91.         d2 = dist(v[0], v[i], v[i + 1])
  92.         if abs(d2) < EPS:
  93.             continue
  94.  
  95.         a2 = dist(Point(0., 0.), v[i], v[i + 1])
  96.         if((d2 > 0 and a2 > EPS) or (d2 < 0 and a2 < -EPS)):
  97.             ok += 1
  98.  
  99.         d3 = dist(v[i], v[i + 1], v[0])
  100.         if abs(d3) < EPS:
  101.             continue
  102.  
  103.         a3 = dist(Point(0., 0.), v[i + 1], v[0])
  104.         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)))):
  105.             ok += 1
  106.  
  107.         if ok == 3:
  108.             return True
  109.  
  110.     return False
  111.  
  112.  
  113. def solve_testcase(t):
  114.     (_, l) = t
  115.  
  116.     v = [Point(m / q, -1.0 / q) for (m,q) in l]
  117.     v = convex_hull(v)
  118.  
  119.     if not origin_in_polygon(v):
  120.         return float("inf")
  121.  
  122.     p = []
  123.     for i in range(len(v)):
  124.         a_1, b_1 = v[i].x, v[i].y
  125.         a_2, b_2 = v[(i + 1) % len(v)].x, v[(i + 1) % len(v)].y
  126.         d = (a_1 * b_2) - (a_2 * b_1)
  127.         p.append( Point((b_1 - b_2) / d, (a_2 - a_1) / d) )
  128.  
  129.     area = 0.
  130.     for i in range(len(p)):
  131.         a = p[i].norm()
  132.         b = p[(i + 1) % len(p)].norm()
  133.         c = (p[i] - p[(i + 1) % len(p)]).norm()
  134.         area += get_area(a, b, c)
  135.  
  136.     return area
  137.  
  138. def solve(input, output):
  139.     for i, t in enumerate(parse_testcases(input)):
  140.         print("Case #%d:" % (i + 1), str(solve_testcase(t)), file=output)
  141.  
  142. if __name__ == "__main__":
  143.     solve(sys.stdin, sys.stdout)
Success #stdin #stdout 0.03s 9600KB
comments (?)
stdin
copy 
2
5
1.0 1.0
-0.3 2.4
-2.9 6.2
0.3 -1.0
-0.9 -1.0
3
-0.3 -0.2
1.0 0.8
0.2 0.6
stdout
copy 
Case #1: 5.621862348178139
Case #2: inf
https://ideone.com/hGS3pI
Reply 2021 Painting - Official
language:
Python 3 (python  3.9.5)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!