After you have made a name for yourself as an architect designing transport systems, you hear about a large contract from the city of Urbopolis, a dense and thriving metropolitan area surrounded by a suburban sprawl. Three major highways pass through the city, allowing travel to and from neighboring cities. The job is to design a Beltway, a highway which will encircle the city's center and allow easy access from any highway to other parts of the city, with the following design constraints and goals:
- The Beltway must be tangent to each highway, without crossing over any highway.
- The Beltway must be perfectly circular.
See how the circular Beltway (in Yellow) touches upon each Highway (in Blue).
However, you notice that it has not been specified which part of the city the Beltway is supposed to be in, and you realize this leaves multiple possible locations for the Beltway to exist while still touching all three highways without crossing.
These Beltways also satisfy the design constraints.
You decide that the best way to win the contract would be to provide all possible solutions as options, and get to work.
Problem Statement
Given the xy coordinates of the three highways, find the circular Beltways
which are tangent to each highway, then return the total area encompassed by each of the four beltways.
Input Data
The first line will be Q, the quantity of testcases.
Q lines will then follow, each with 12 space-separated values in the format H1x H1y H2x H2y H3x H3y H4x H4y H5x H5y H6x H6y,
being the xy 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),
and the coordinates of two points along the third highway (H5x, H5y), (H6x, H6y).
Answer
Should consist of Q space-separated values, corresponding to total sum area enclosed by the the four possible Beltways in each testcase.
Error should be less than 1e-4.
Example
input data:
2
5 9 -6 8 3 6 7 -4 6 3 1 -2
-7 0 2 -10 -8 -7 0 -9 0 7 2 -7
answer:
797.185
24.507