Craters

This problem asks you to find the length of the convex hull which never passes within a given distance of a set of circles.

Idea: take convex hull of circle centers to determine which form the "vertices" of the hull. Then compute the actual length of the hull. Problem: what if there are two super wide circles consecutively on the hull, and a narrower circle between them which is NOT on the ultimate hull, but IS on the hull of centers? This is not sufficient to determine which circles form the hull.

Simplification: increase the radius of the circles by the "gap" distance and then don't worry about the gap anymore.

We know that the hull will be composed of lines which are tangent to pairs of circles, and then distance on the circle between them. If we can determine which circles are on the hull, the problem is "trivial."

Intuition: the only "interesting" points are the intersections of lines tangent to two circles and the circles themselves.

IF that's the case, just calculate all those intersections, run convex hull to figure out which ones are on the hull, and then "fix it up" for the bits that are on the edge of a circle itself.

1. Calculate lines tangent to all pairs of circles.
   1. for each pair, determine the tangent point to each circle.
      • Note that the line tangent to a circle and the radius from the center of the circle to that tangent point form a right angle
      • if you draw a line parallel to the tangent line from the center of one circle to the extension of the radius from the previous step, this forms a right triangle (because right angles and parallel lines!) Two edge lengths are known and are
        1. The difference between the lengths of the radii
        2. the distance between the circles
      • The angle formed at the center of the first circle between the line we just drew and the line connecting the two centers can be determined using the two known edge lengths and the law of sines
      • We can use this angle to compute everything else we need to know, including the tangent points
      • Note that each pair of circles will have TWO tangent lines, one on each side, symmetric about the line between their centers
   2. add the tangent points to a list
2. compute the convex hull of tangent points
3. walk the calculated hull
   1. For each segment which spans circles, simply add the length
   2. for a segment which would form a chord of a circle (i.e. the parts between tangent lines), compute the angle between the two consecutive points, and add the circumference of the circle times that angle over 2*pi