Gear Set
Time Limit: 1 Second Memory Limit: 32768 KB
Sunny Cup 2003 - Preliminary Round
April 20th, 12:00 - 17:00
Problem G: Gear Set
A group of gears is defined as a set of 2-dinemsional disks with the teeth being
ignored. Each gear can only rotate either clockwise or anti-clockwise according
to a fixed axes. The gears are not overlapping each other. If one gear is rotating
clockwise, then another one which is tangent to it will rotate anti-clockwise,
and vice versa. Here we assume that the gears will never skid.
Given the centers and radiuses of n gears which are indexed from 1 to n. One
questions is: will the n-th gear be driven by the 1st gear if we rotate the
1st one clockwise?
In Figure 1, the 1st gear is stuck so it cannot be rotated at all. In Figure
2, the n-th (3rd) gear is not tangent to any of the other gears and hence will
not be driven by the 1st one.
If it is possible to drive gear n by gear 1, then let us rotate gear 1 clockwise
with a steady speed. Assume that there is a worm initially sticking at the left-most
point (the 2-D point with the smallest x coordinate) on gear 1. When the worm
is driven to a tangent point to another gear, it can jump to the other gear
or stay where it is. What is the minimum distance that worm must travel, if
it is to reach the right-most point on gear n? Please keep in mind that the
worm can be driven by a gear only, not by itself.
Input
The input consists of several test cases. In each test case:
the first line contains an integer n (2 <= n <= 20), which is the number of
gears;
and the following n lines gives the information of the n gears, each occupies
one line. To be more specific, in the i-th line, there are xi and yi, the coordinates
of the i-th disk center, and the radius ri of the i-th disk.
Note:
xi, yi, and ri are all floating point numbers.
Two disks (x1, y1, r1) and (x2, y2, r2) are considered to be tangent to each
other, if fabs(r1 + r2 - dist) < 1e-5, where dist is the distance between their
centers.
The input is finished by n = -1.
Output
For each test case, if gear n cannot be driven by gear 1, print "Wrong combination"; otherwise print the minimum distance that the worm must move, up to 3 decimal places.
Sample Input
3 0 0 1 2 0 1 1 1.7320508 1 4 0 0 1 2 0 1 0 2 1 2 2 1 -1
Sample Output
Wrong combination 6.283Submit
Source: Zhejiang University Local Contest 2003, Preliminary