After your success as an Architect designing a new Metro Loop for the coastal city of Apollon, you have now been commissioned by the inland city of Geon.
A few years ago Geon was just a remote town with little reason to attract visitors, being connected to the distant highways by dirt roads. However after a major discovery of Orichalcum mines found nearby, people have been flocking to the city. The dirt roads were not meant to accommodate so many travelers and have degraded to a terrible condition - muddy, uneven, and filled with potholes.
Your job is to design a new paved road which will connect Geon to the two closest highways, allowing vehciles to travel safely from the highway to the city. Formally, the city has the following requests for the new road:
- It must be a perfect circle.
- It must pass directly through the center of Geon.
- It must be tangent to both highways, but not cross them. There is a budget for on/off ramps, but not for overpasses.
Also just like last time, there will always be two possible circles which are tangent to each highway and pass through the city. They want you to design both circles before they approve any plans.
See how each circular paved road (in Yellow) passes through Geon (in Red),
and also touches upon each Highway (in Blue).
Problem Statement
Given the xy coordinates of Geon and the two highways, find the circles
which intersect Geon and are tangent to each highway, then return the xy coordinates of each circle's centerpoint.
Input Data
The first line will be Q, the quantity of testcases.
Q lines will then follow, each with eight space-separated values in the format Gx Gy H1x H1y H2x H2y H3x H3y,
being the xy coordinates of Geon (Gx, Gy), the coordinates of two points along the first highway
(H1x, H1y), (H2x, H2y), and also the coordinates of two points along the second highway (H2x, H2y), (H3x, H3y),
Note that both highways share the point (H2x, H2y).
Answer
Should consist of Q sets of 4 space-separated values each, corresponding to xy coordinates of the centerpoints of
both circular loops which intersect the given point and are also tangent to the given lines.
For each testcase, the order in which you report the circle centerpoints will not matter - the checker will accept them in either order.
Error should be less than 1e-4.
Example
input data:
2
5 9 3 6 6 3 8 4
-71 -43 -47 28 66 -14 10 72
answer:
6.576 6.547 10.824 32.727
6.864 -87.922 -1250.964 -1659.901