As cities grow larger, traffic congestion quickly becomes an issue due to more people driving more vehicles on the roads. When urban centers become especially dense, traffic may become gridlocked or see a spike in vehicle collisions. Dealing with city congestion is a common problem for city planners, and providing public transportation is often a common solution. It's no coincidence that all of the largest urban centers on the planet also have some sort of underground Mass Rapid Transit system, commonly called a Subway or Metro System. These underground railways allow large groups of people to easily travel to key points within a city, without causing any congestion on the roads.
A large city will often have multiple of these railways to allow residents to quickly travel through different parts of the city. Some railways, called Lines, have railcars which will travel from point A to point B, then reverse direction and travel back from point B to point A, allowing passengers to make stops as stations along the way. Other railways, called Loops, will have continuous travel in a single direction, allowing passengers to make stops at stations along the loop.
A diagram of the 1955 Moscow Metro System.
Let's imagine you are an Architect designing the path for a new Metro system which will run underneath the city of Apollon. The railway's path must pass through the two existing stations in the commercial and residental districts. There is also a perfectly straight boardwalk which runs along the coast, upon which a station is planned to be built although its exact location on the boardwalk hasn't been determined. However it is critical that the station is on the boardwalk to allow easy access to the coast, but it is also critical that the railway path does not cross beyond the boardwalk, or else the coastal waters will flood the tunnels!
Additionally, to allow for a pleasing visual experience for commuters reading Metro maps, you've been challenged to make the railway path be a perfectly circular loop. Also, your supervisor tells you that given all these conditions, there should be exactly two circular loops possible - he wants you to find both.
See how the each circular railway (in Yellow) passes through the Residential Station (in Red),
the Commercial Station (in Green), and also touches upon to the boardwalk (in Blue).
Problem Statement
Given the xy coordinates of two railway stations and one line onto which a third station will be built, find the circle
which intersects the two stations and is tangent to the line, and return the xy coordinates of its center.
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 Rx Ry Cx Cy B1x B1y B2x B2y, being the xy
coordinates of the Residential District station (Rx, Ry), the Commercial District station (Cx, Cy), and also the
coordinates of two arbitrary points along the straight Boardwalk (B1x, B1y), (B2x, B2y).
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 (Rx, Ry) and (Cx, Cy), and are also tangent to the line intersecting (B1x, B1y) and (B2x, B2y).
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:
3
5 1 3 7 10 7 1 10
5 1 3 7 10 7 1 10
4 -10 -4 -5 20 8 -2 11
answer:
-6.167 0.611 5.729 4.576
5.729 4.576 -6.167 0.611
4.679 -0.013 -108.237 -180.678