sweeneyde

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

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.

×