sweeneyde

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
  124. main(stdin.read())
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×