After having earned your reputation as a master of public transportation planning, your services have once again been requested to connect a remote town to two existing train systems. You recall your previous experience in providing access from a town to two straight highways, though this time the train railways you must provide access to are circular. The desired new loop will pass through the town and will also be tangent to both existing railway loops.
See how the solution circles (in Yellow) each pass through the given Town (in Blue), and are tangent to each existing circular railway (in Green).
Problem Statement
Given the xy coordinates of a given point, and also the xy coordinates and radii of two given circles,
find all possible solution circles which pass through the given point and are tangent to both given circles.
Report the sum of the radii of all possible solution circles in each testcase.
Input Data
The first line will be Q, the quantity of testcases.
Q lines will then follow, each with 8 space-separated values in the format Px Py C1x C1y C1r C2x C2y C2r,
being the coordinates of the given point (Px, Py),
the xy coordinates of the first given circle (C1x, C1y),
the radius of the first given circle C1r,
the xy coordinates of the second given circle (C2x, C2y),
and the radius of the second given circle C2r).
Answer
Should consist of Q space-separated values each, corresponding to the sum of the radii of all possible
solution circles for each testcase.
If no solution circles are possible for a given testcase, report 0 for that case instead.
Error should be less than 1e-4.
Example
input data:
5
1 2 -3 -4 5 -4 5 3
1 -2 -3 -4 5 -4 5 3
1 -2 -3 -4 5 0 0 4
-5 4 -3 -4 5 0 0 4
-5 0 -3 -4 7 0 -3 3
answer:
X X X X X