After having designed circular Bike Paths for the city of Urbopolis, you are now tasked with designing a loop for a high-speed Maglev Train. Meglev is short for Magnetic Levitation, as these trains use magnets to "float" above the rails, instead of making physical contact with the rails on rolling wheels. Because there is no physical contact between the train and the rails to cause friction, these trains can reach extremely high speeds.
The specific loop that you will be designing will be intended for commuters travelling from an existing station in a Residential neighborhood, to either the city's circular Beltway or to the straight Highway. As before, there is large cost associated with building bridges or tunnels, and so the Maglev loop should not cross over the Beltway nor the Highway.
See how the circular Maglev Loop (in Yellow) runs through the Residential neighborhood (in Red),
and is tangent to both the Beltway (in Green) and the Highway (in Blue).
Sometimes there are multiple possible solutions.
But sometimes there are no possible solutions.
Problem Statement
Given the xy coordinates of the Residential station, the xy coordinates and radius
of the Beltway, and the xy coordinates of two points along the Highway, find all possible circular Maglev loops
which pass through both the Residential Station, and also are tangent to both the Beltway and the Highway.
Report the sum of the radii of all possible Meglev Loops given the aboven information.
Input Data
The first line will be Q, the quantity of testcases.
Q lines will then follow, each with 9 space-separated values in the format Rx Ry Bx By Br H1x H1y H2x H2y,
being the xy coordinates of the Residential Station (Rx, Ry),
the xy coordinates of the center of the circular Beltway (Bx, By),
the radius of the Beltway Br,
and two points along the straight Highway (H1x, H1y) and (H2x, H2y).
Answer
Should consist of Q space-separated values, corresponding to the sum of the radii of all possible Meglev loops
in each givne testcase.
If a given testcase has no possible Maglev Loops, then report 0.
Error should be less than 1e-4.
Example
input data:
5
1 2 -3 -4 5 6 -4 5 3
1 -2 -3 -4 5 6 -4 5 3
1 -2 -3 -4 5 6 3 3 4
-2 4 -3 -4 5 6 -4 5 3
1 -2 -3 -4 5 6 0 0 4
answer:
15.375 0 19.677 0 3.177