Having just completed your most recent project designing a loop to connect a remote village to two circular railways, you soon hear about another exciting project. A few years ago, a remote town in the desert decided to give tax breaks to any casinos wishing to open in their town, and within a few years it has transformed into a bustling and sprawling city. However, because the town is in the middle of a desert, the highways are far away and the only convenient way to get there is by airplane. With the city now having grown large, importing good is become expensive, and so the city wants to design a railway loop from their city to each nearest highway. And the Casino City is large enough that the railway should connect with its beltway.
See how all the possible desired railways (in Yellow) are tangent to both Highways (in Blue),
and also are tangent to the City's Beltway (in Red).
Problem Statement
Given the one circular Beltway and two straight Highways, find all possible solution circles which are tangent to the given Beltway and are also tangent to both given Highways. 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 11 space-separated values in the format H1x H1y H2x H2y H3x H3y H4x H4y Bx By Br,
being the coordinates of two points along the first highway (H1x, H1y), (H2x, H2y),
the coordinates of two points along the second highway (H3x, H3y), (H4x, H4y),
the xy coordinates of the center of the given circular beltway (Bx, By),
and the radius of that beltway Br).
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
X
X
X
X
X
answer:
X X X X X