Line & Circle Maze

A deranged algorithms professor has devised a terrible final exam. He drops his students into a strange maze built entirely from straight line segments and circles. The junctions of the maze are the endpoints of the line segments, together with every point where two objects (segments or circles) intersect.

The professor hands out a map of the maze and puts a fixed amount of time on the clock. Any student still inside when the time runs out is instantly inverted at the quantum level. Because he knows that clever programming students always walk the shortest possible route between two junctions, he picks the entrance and exit junctions so that the distance a student must travel is as long as possible: among all pairs of junctions connected by some path, he chooses the pair whose shortest-path distance is the largest.

Computing that longest shortest-path length is tedious, so he wants you to do it. Given a collection of line segments and circles, determine the shortest path between every pair of junctions and report the length of the longest such shortest path.

The maze generator guarantees:

1. No endpoint of a line segment lies on a circle.
2. No line segment is tangent to a circle.
3. If two circles intersect, they intersect at exactly two distinct points.
4. Every maze has at least two junctions (the smallest maze is either a single line segment, or two intersecting circles).

The maze is not necessarily connected: some segments or circles (or whole sub-mazes) may stand apart from the rest. The length you report must be for a path between two junctions that are actually connected.

Example maze shapes include: a maze of line segments only; a maze of circles only (where more than one pair of junctions may share the same longest shortest path); a maze split into disconnected components; and a maze in which line segments are linked by a circle, allowing a longer shortest path.

Each test case is a collection of line segments and circles, one object per line.

• A line segment is given as L X1 Y1 X2 Y2, where L is a literal character and (X1, Y1) and (X2, Y2) are its endpoints.
• A circle is given as C X Y R, where C is a literal character, (X, Y) is its center, and R is its radius.

All values are integers. Every segment and circle lies entirely inside the first-quadrant box with corners (0, 0) at the lower left and (100, 100) at the upper right. Each test case has from 1 to 20 objects and is terminated by a line containing only a single asterisk (*). After the final test case, one more line containing only a single asterisk marks the end of the input.

For each maze, print Case N: , where N is the test-case number starting from 1, followed by the length of the longest shortest path between a pair of connected junctions, rounded to one decimal place.

When computing arc angles, prefer atan2() over acos() or asin().