For the UCF High School Programming Tournament, the judges were located in the Engineering building, and most of the teams were in the Classroom building, which is on the other side of Pegasus Circle.
Chris was walking to the Classroom building for the first time, and was joined by Jeremy, who had made the hike a couple of times already.
“Jeremy, is it faster to stay on the circle, or to cut through the middle using the boardwalks that go to the Student Union?” asked Chris.
“I don’t know.” Jeremy answered. “I think it’s about the same, but it might be slightly faster to use the walkways.”
“Well, if it’s about the same, let’s stick to the circle. I don’t want to be attacked by squirrels.”*
Given two points on a circle, and two paths to get from one to the other—one following the perimeter of the circle, and the other by a sequence of connected straight line segments through the interior of the circle—determine the shorter of the two paths.
The input will contain multiple test cases, each consisting of two lines. The first line of each test case contains six floating-point numbers: xc, yc, xs, ys, xf, and yf, where (xc, yc) is the center point of the circle, (xs, ys) is the start point for both paths (e.g., the Engineering building), and (xf, yf) is the finish point for both paths (e.g., the Classroom building). The circle will always have a radius greater than 1, and the start and finish points are both guaranteed to be at distinct points on its perimeter, with an accuracy of at least 3 places after the decimal. The path along the perimeter is always in the direction counter-clockwise around the circle.
The second line of each test case will start with an integer, n (1 ≤ n ≤ 10), followed by n pairs of floating-point numbers, x1, y1, x2, y2, … xn, and yn, where each pair (xi, yi) is a point inside the circle. The interior path traveled will be from point (xs, ys) to point (x1, y1), then from (x1, y1) to (x2, y2), then from (x2, y2) to (x3, y3), …, then from (xn, yn) to (xf, yf).
The last test case will be followed by a line containing six zeros. All numbers on an input line will be separated from each other by one space, with no extra spaces at the beginning or end of lines. Assume that all the input floating point numbers will be less than 1000.0 and greater than -1000.0, with at most 6 places after the decimal.
For each test case in the input, output a line in either the format
Case #n: Stick to the Circle.
if the perimeter path is shorter, or
Case #n: Watch out for squirrels!
if the interior path is shorter, where n is the number of the input test case, starting at 1.
Assume that the two paths will not be equal, i.e., it is guaranteed that the two distances will not be equal. In particular, assume that the two paths will differ in length by 0.001 or more.
Leave a blank line after the output for each test case.
5.0 5.0 10.0 5.0 5.0 10.0
6 8.5 4.7 6.9 5.0 3.6 6.5 4.2 7.1 4.2 8.3 4.7 8.8
2.0 8.0 0.5 16.87412 7.5 0.8761
2 3.25 9.25 7.0 7.0
0 0 0 0 0 0
Case #1: Stick to the Circle.
Case #2: Watch out for squirrels!
1&2) Sample data
3) Biggest circle
4) Smallest circle
5&6) Same start and end points, but swapped; segments will be shorted for one but not the other (cw vs. ccw)
7) Biggest circle, going from start to middle, back to start, to end
8) Biggest circle, going from start to near middle, back to start, to end (which is still shorter than the arc)
9&10) Center at (-pi, -pi) radius=2, start to end is vertical. These cases are intended to make them get a negative value
for the angle between start and end (for one of the two cases) in order to get a negative arc length
11) Same as previous, except there are 10 points inside the circle given, all of them the same exact point
(which is valid by the specification)
12&13) Very tiny angle, cw and ccw
14) start over end vetically, ten intra-circle points that lie extremely close to (0,0)
15) circle has radius = pi, intra-circle segments create a path with vertical and horizonal lines
16) arc makes non-right, obtuse angle; intra-circle path is long and useless
17) intra-circle path goes directly to within 0.000001 of the end, then back to the start
18) the arc wins by 0.002
19) the intra-circle path wins by 0.002