George a shepherd living in a large meadow. During the day he keeps a watchful eye to protect his flock of sheep, but at night the hungry wolves prowl, looking for opportunities to snatch up unsuspecting sheep. To keep the sheep safe while he is sleeping at night, George plans to construct a large fence to keep the wolves out.
However there are four large boulders randomly positioned in the field where George wants to build the fence. If he builds the fence too close to the boulders then either the wolves could jump over and get in, or the sheep could jump over and get out (if some bold sheep wanted a midnight graze, for example). George wants to build his circular fence such that each boulder is exactly the same distance away from the fence's edge. Additionally, he wants to make sure that two of the boulders end up inside the fence, and two end up on the outside of the fence.
Note how each blue point is the same distance from the edge of the yellow circle,
with two points being inside the fence and the other two outside the fence.
Problem Statement
Given the (x, y) coordinates of four boulders in a field, calculate the radius
and position of the circlar fence which is equidistant to each boulder, and contains
only two boulders.
Each testcase will have multiple valid solutions. Return any one of them.
Input Data
First line will be Q, the quantity of testcases.
Q lines will follow, each with eight space-separated values in the format
x1 y1 x2 y2 x3 y3 x4 y4 describing the (x, y) coordinates of four points.
Answer
Should consist of 3 * Q space-separated values, corresponding to the radius and
(x, y) centerpoint coordinates of the circle equidistant to each given point.
Error should be less than 1e-6.
Example
input data:
2
0 1 -2 3 4 5 6 -7
0.1 2.3 4.5 6.7 8.9 -8.7 -6.5 -4.3
answer:
9.729574 -5.8 -2.8 8.467057 -1 -3.2