After your success in building the Urbopolis Beltway, the Urbopolis City Director of Public Health approaches you. They inform you of many recent scientific studies which have been performed, and the results indicate that the health of the city's populace is in decline! They have further determined that the cause is the increased amount of time that people now spend in their cars driving around, instead of being physically active. The Director proposes a solution - a huge Bike Path which will lead through the most beautiful parts of the city.
He lays out his grand plan - the path will lead through the city's largest park so that the residents may get plenty of fresh air, and it will also lead through the historic section of the city so that they may marvel at the beautiful old buildings. And the path must be accessible to all, so it should be adjacent to that circular beltway that you just recently built. However you should take care that the bike path should not cross the highway, which would be quite dangerous! And to keep with the general theme of your designs, he envisions the path being a perfect circle.
After giving it some thought, you come to the conclusion that given the positions of the two points and Beltway, there are sometimes a variety of possible solutions. Sometimes it might not be possible to design any valid Bike Path at all!
See how the circular Bike Paths (in Red) run through the Park (in Green), the Historic Section (in Blue), and also touches upon the Beltway (in Yellow).
These Bike Paths are also valid.
Both of these Bike Paths exist within the Beltway!
There is no valid circular bike path possible in this layout.
The Director is only interested in the largest bike path possible. If two paths are possible, then ignore the smaller one and only report the centerpoint of the larger one.
Problem Statement
Given the xy coordinates of the Park and Historic Section, along with the xy coordinates and radius
of the Beltway, find all possible circular Bike Paths which pass through both the Park and Historic Section,
and also are tangent to the Beltway.
If two Bike Paths are possible, report the x y centerpoint coordinates of the larger one.
If one Bike Path is possible, its x y centerpoint coordinates.
If zero Bike Paths are possible, report the x y centerpoint coordinates as X X.
Input Data
The first line will be Q, the quantity of testcases.
Q lines will then follow, each with 7 space-separated values in the format Px Py Hx Hy Bx By Br,
being the xy coordinates of the Park (Px, Py), the coordinates of the Historic Section (Hx, Hy),
the coordinates of centerpoint of the Beltway (Bx, By),
and the radius of the Beltway Br.
Answer
Should consist of Q sets of 2 space-separated values each, corresponding to x y coordinates of
the largest possible Bike Path in each testcase.
If a given testcase has no possible Bike Paths, then the characters X X should be reported instead.
Error should be less than 1e-4.
Example
input data:
4
2 2 -2 1 4 1 2
1 -1 8 2 4 1 2
1 2 3 4 5 6 4
3 -1 2 0 4 -1 3
answer:
-1.479 7.415 2.654 4.807 X X 3.412 0.412