# Untitled

Mar 3rd, 2021
877
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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