A Henge is a stone-age structure often consisting of large monoliths or other features (such as timber holes) arranged in a circular pattern and sometimes with a large feature in the center of the circle as well.
Stonehenge in England - the most famous of all henges.
Because these structures are so ancient, many features are at risk of disappearing over time. For example if logs were once set into deep holes in the ground then eventually the wood would rot away and the hole may fill in.
Let's imagine you are an amateur archaeologist, wandering the meadows searching
for any possible remnants of yet-undiscovered henges. After a good deal of walking
around you manage to find 3 holes in the ground that you suspect may be old
timber holes. To confirm your theory, you plan to locate the center of the ring
formed by the positions of these three holes, and see if you can get lucky and
find a large monolith in that location. If no megalith is present, then maybe the
holes were made by rabbits instead...
Problem Statement
You will be given a set of 3 coordinates in the x-y plane, corresponding to
three points lying on the edge of a circle. Return the position of the center of
that circle.
Input Data
First line will be Q, the quantity of testcases.
Q lines will follow, each describing a set of 3 points in the format x1 y1 x2 y2 x3 y3.
Answer
Should consist of 2 * Q space-separated values, with each (x, y) coordinate
pair corresponding to the center of the circle described by each testcase.
Error should be less than 1e-6
Example
input data:
2
1 2 4 3 5 6
1.234 -5.678 -9.876 4.321 -1.357 8.642
answer:
1.5 5.5 -2.826869 0.981646