Advertisement
sweeneyde

Untitled

Mar 3rd, 2021
1,092
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.49 KB | None | 0 0
  1. import math
  2. import collections
  3.  
  4. Circle = collections.namedtuple('Circle', 'x y r')
  5. Point = collections.namedtuple('Point', 'x y c')
  6.  
  7.  
  8. # https://en.wikipedia.org/wiki/Tangent_lines_to_circles#Outer_tangent
  9. # TODO test intersecting circles and stuff
  10. def outer_tangents(alpha, c1, c2):
  11.     s = math.sin(alpha)
  12.     c = math.cos(alpha)
  13.     x3 = c1.x + c1.r * s
  14.     y3 = c1.y + c1.r * c
  15.     x4 = c2.x + c2.r * s
  16.     y4 = c2.y + c2.r * c
  17.     x32 = c1.x - c1.r * s
  18.     y32 = c1.y - c1.r * c
  19.     x42 = c2.x - c2.r * s
  20.     y42 = c2.y - c2.r * c
  21.     return [Point(x3, y3, c1), Point(x4, y4, c2),
  22.             Point(x32, y32, c1), Point(x42, y42, c2)]
  23.  
  24.  
  25. def tangents(c1, c2):
  26.     if c1.r > c2.r:
  27.         c1, c2 = c2, c1
  28.     gamma = -math.atan2(c2.y - c1.y, c2.x - c1.x)
  29.     beta = math.asin((c2.r - c1.r) / math.hypot(c2.x - c1.x, c2.y - c1.y))
  30.     points = outer_tangents(gamma - beta, c1, c2)
  31.     points1 = outer_tangents(gamma + beta, c1, c2)
  32.     points.extend(points1)
  33.     return points
  34.  
  35.  
  36. def turnLeft(p1, p2, p3):
  37.     dx1 = p2.x - p1.x
  38.     dx2 = p3.x - p2.x
  39.     dy1 = p2.y - p1.y
  40.     dy2 = p3.y - p2.y
  41.     return dx1 * dy2 >= dx2 * dy1
  42.  
  43.  
  44. def hull_one_side(points):
  45.     hull = []
  46.     for point in points:
  47.         while len(hull) >= 2 and turnLeft(hull[len(hull) - 2], hull[len(hull) - 1], point):
  48.             hull.pop()
  49.         hull.append(point)
  50.     return hull
  51.  
  52.  
  53. def convex_hull(points):
  54.     points.sort()
  55.     no_duplicates = [points[0]]
  56.     for i in range(1, len(points)):
  57.         if math.hypot(no_duplicates[-1].x - points[i].x, no_duplicates[-1].y - points[i].y) > 1e-14:
  58.             no_duplicates.append(points[i])
  59.     h1 = hull_one_side(no_duplicates)
  60.     no_duplicates.reverse()
  61.     h1.pop()
  62.     h2 = hull_one_side(no_duplicates)
  63.     h2.pop()
  64.     h1.extend(h2)
  65.     return h1
  66.  
  67.  
  68. def contains(c1, c2):
  69.     # Check if c1 contains c2
  70.     dr = c1.r - c2.r
  71.     dist = math.hypot(c1.x - c2.x, c1.y - c2.y)
  72.     return dr >= dist
  73.  
  74.  
  75. def main(string):
  76.     lines = iter(string.splitlines())
  77.     n = int(next(lines))
  78.  
  79.     circles = []
  80.     for row in lines:
  81.         x, y, r = map(int, row.split(" "))
  82.         circle = Circle(x, y, r + 10)
  83.         if any(contains(c, circle) for c in circles):
  84.             continue
  85.         circles[:] = [c for c in circles if not contains(circle, c)] + [circle]
  86.  
  87.     if len(circles) == 1:
  88.         print(circles[0].r * 2 * math.pi)
  89.         return
  90.  
  91.     points = []
  92.     for i in range(len(circles)):
  93.         for j in range(i + 1, len(circles)):
  94.             points.extend(tangents(circles[i], circles[j]))
  95.     points = convex_hull(points)
  96.     points = [
  97.         p for p in points
  98.         if not any(
  99.             (p[0]-x)**2 + (p[1]-y)**2 < r**2
  100.             for x, y, r in circles
  101.         )
  102.     ]
  103.     # from pprint import pprint
  104.     # pprint([(x, y) for (x, y, _) in points])
  105.     # pprint([(x, y) for (x, y, _) in convex_hull(points)])
  106.     total_d = 0
  107.     for i in range(len(points)):
  108.         p1 = points[i]
  109.         p2 = points[(i + 1) % len(points)]
  110.         if p1.c == p2.c:
  111.             circ = p1.c
  112.             p1_angle = math.atan2(p1.y - circ.y, p1.x - circ.x)
  113.             p2_angle = math.atan2(p2.y - circ.y, p2.x - circ.x)
  114.             total_angle = (p1_angle - p2_angle) % math.tau
  115.             assert total_angle > 1e-8
  116.             total_d += total_angle * circ.r
  117.         else:
  118.             d = math.hypot(p1.x - p2.x, p1.y - p2.y)
  119.             # print(d)
  120.             total_d += d
  121.     print(total_d)
  122.  
  123. from sys import stdin
  124. main(stdin.read())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement