Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import math
- import collections
- Circle = collections.namedtuple('Circle', 'x y r')
- Point = collections.namedtuple('Point', 'x y c')
- # https://en.wikipedia.org/wiki/Tangent_lines_to_circles#Outer_tangent
- # TODO test intersecting circles and stuff
- def outer_tangents(alpha, c1, c2):
- s = math.sin(alpha)
- c = math.cos(alpha)
- x3 = c1.x + c1.r * s
- y3 = c1.y + c1.r * c
- x4 = c2.x + c2.r * s
- y4 = c2.y + c2.r * c
- x32 = c1.x - c1.r * s
- y32 = c1.y - c1.r * c
- x42 = c2.x - c2.r * s
- y42 = c2.y - c2.r * c
- return [Point(x3, y3, c1), Point(x4, y4, c2),
- Point(x32, y32, c1), Point(x42, y42, c2)]
- def tangents(c1, c2):
- if c1.r > c2.r:
- c1, c2 = c2, c1
- gamma = -math.atan2(c2.y - c1.y, c2.x - c1.x)
- beta = math.asin((c2.r - c1.r) / math.hypot(c2.x - c1.x, c2.y - c1.y))
- points = outer_tangents(gamma - beta, c1, c2)
- points1 = outer_tangents(gamma + beta, c1, c2)
- points.extend(points1)
- return points
- def turnLeft(p1, p2, p3):
- dx1 = p2.x - p1.x
- dx2 = p3.x - p2.x
- dy1 = p2.y - p1.y
- dy2 = p3.y - p2.y
- return dx1 * dy2 >= dx2 * dy1
- def hull_one_side(points):
- hull = []
- for point in points:
- while len(hull) >= 2 and turnLeft(hull[len(hull) - 2], hull[len(hull) - 1], point):
- hull.pop()
- hull.append(point)
- return hull
- def convex_hull(points):
- points.sort()
- no_duplicates = [points[0]]
- for i in range(1, len(points)):
- if math.hypot(no_duplicates[-1].x - points[i].x, no_duplicates[-1].y - points[i].y) > 1E-14:
- no_duplicates.append(points[i])
- h1 = hull_one_side(no_duplicates)
- no_duplicates.reverse()
- h1.pop()
- h2 = hull_one_side(no_duplicates)
- h2.pop()
- h1.extend(h2)
- return h1
- def contains(c1, c2):
- # Check if c1 contains c2
- dr = c1.r - c2.r
- dist = math.hypot(c1.x - c2.x, c1.y - c2.y)
- return dr >= dist
- if __name__ == "__main__":
- n = int(input())
- circles = []
- for i in range(n):
- x, y, r = map(int, input().split(" "))
- circle = Circle(x, y, r + 10)
- if any(contains(c, circle) for c in circles):
- continue
- circles[:] = [c for c in circles if not contains(circle, c)] + [circle]
- if len(circles) == 1:
- print(circles[0].r * 2 * math.pi)
- else:
- points = []
- for i in range(len(circles)):
- for j in range(i + 1, len(circles)):
- points.extend(tangents(circles[i], circles[j]))
- points = convex_hull(points)
- from pprint import pprint
- pprint([(x, y) for (x, y, _) in points])
- total_d = 0
- for i in range(len(points)):
- p1 = points[i]
- p2 = points[(i + 1) % len(points)]
- if p1.c == p2.c:
- circ = p1.c
- p1_angle = math.atan2(p1.y - circ.y, p1.x - circ.x)
- p2_angle = math.atan2(p2.y - circ.y, p2.x - circ.x)
- total_angle = (p1_angle - p2_angle) % math.tau
- assert total_angle > 1e-8
- total_d += total_angle * circ.r
- else:
- d = math.hypot(p1.x - p2.x, p1.y - p2.y)
- # print(d)
- total_d += d
- print(total_d)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement