OpenKattis
Increasing CP5 Lower Bound (Day 1)

Start

2020-12-06 19:00 AKST

Increasing CP5 Lower Bound (Day 1)

End

2020-12-07 00:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -410 days 4:53:18

Time elapsed

5:00:00

Time remaining

0:00:00

Problem A
Brocard Point of a Triangle

The Brocard point of a triangle $ABC$ is a point $P$ in the triangle chosen so that: $\angle PAB = \angle PBC = \angle PCA$ (see figure below).

\includegraphics[width=0.3\textwidth ]{triangle1.png} \includegraphics[width=0.3\textwidth ]{triangle2.png}

The common angle is called the Brocard angle. The largest Brocard angle is $\pi /6$ which is the Brocard angle for an equilateral triangle (the Brocard point is the centroid of the triangle).

Write a program to compute the coordinates of the Brocard point of a triangle given the coordinates of the vertices.

Input

The first line of input contains a single integer $P$, ($1 \le P \le 600$), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input. It contains the data set number, $K$, followed by the six space separated coordinate values $A_ x, A_ y, B_ x, B_ y, C_ x, C_ y$ of the vertices of the triangle, which are in the range ($-20 \le A_ x, A_ y, B_ x, B_ y, C_ x, C_ y \le 20$). The vertices will always be specified so going from $A$ to $B$ to $C$ and back to $A$ circles the triangle counter-clockwise. Input coordinates are floating point values with up to 4 digits after the period.

Output

For each data set there is a single line of output. The single output line consists of the data set number, $K$, followed by a single space followed by the $x$ coordinate of the Brocard point, followed by a single space followed by the $y$ coordinate of the Brocard point. The coordinates are considered correct if their individual absolute or relative error does not exceed $10^{-5}$.

Sample Input 1 Sample Output 1
3
1 0 -1.3 3.4 0.5 1.1 2.3
2 0 0 3 0 0 4
3 3.1 0.2 4.3 0.4 0 0.8
1 1.404561 0.828896
2 1.560468 0.749025
3 3.876994 0.401673