# Untitled

Mar 3rd, 2021
835
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. if __name__ == "__main__":
76.     n = int(input())
77.     circles = []
78.     for i in range(n):
79.         x, y, r = map(int, input().split(" "))
80.         circle = Circle(x, y, r + 10)
81.         if any(contains(c, circle) for c in circles):
82.             continue
83.         circles[:] = [c for c in circles if not contains(circle, c)] + [circle]
84.
85.     if len(circles) == 1:
86.         print(circles[0].r * 2 * math.pi)
87.     else:
88.         points = []
89.         for i in range(len(circles)):
90.             for j in range(i + 1, len(circles)):
91.                 points.extend(tangents(circles[i], circles[j]))
92.         points = convex_hull(points)
93.         from pprint import pprint
94.         pprint([(x, y) for (x, y, _) in points])
95.
96.         total_d = 0
97.         for i in range(len(points)):
98.             p1 = points[i]
99.             p2 = points[(i + 1) % len(points)]
100.             if p1.c == p2.c:
101.                 circ = p1.c
102.                 p1_angle = math.atan2(p1.y - circ.y, p1.x - circ.x)
103.                 p2_angle = math.atan2(p2.y - circ.y, p2.x - circ.x)
104.                 total_angle = (p1_angle - p2_angle) % math.tau
105.                 assert total_angle > 1e-8
106.                 total_d += total_angle * circ.r
107.             else:
108.                 d = math.hypot(p1.x - p2.x, p1.y - p2.y)
109.                 # print(d)
110.                 total_d += d
111.         print(total_d)
RAW Paste Data