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