Geometry Problem

Alice is interesting in computation geometry problem recently. She found a interesting problem and solved it easily. Now she will give this problem to you :

You are given $N$ distinct points $(X_i,Y_i)$ on the two-dimensional plane. Your task is to find a point $P$ and a real number $R$, such that for at least $\lceil \frac{N}{2} \rceil$ given points, their distance to point $P$ is equal to $R$.

The first line is the number of test cases.

For each test case, the first line contains one positive number $N(1 \leq N \leq 10^5)$.

The following $N$ lines describe the points. Each line contains two real numbers $X_i$ and $Y_i$ $(0 \leq |X_i|, |Y_i| \leq 10^3)$ indicating one give point. It's guaranteed that $N$ points are distinct.

For each test case, output a single line with three real numbers $X_P, Y_P, R$, where $(X_P,Y_P)$ is the coordinate of required point $P$. Three real numbers you output should satisfy $0 \leq |X_P|, |Y_P|, R \leq 10^9$.

It is guaranteed that there exists at least one solution satisfying all conditions. And if there are different solutions, print any one of them. The judge will regard two point's distance as $R$ if it is within an absolute error of $10^{-3}$ of $R$.

1
7
1 1
1 0
1 -1
0 1
-1 1
0 -1
-1 0

0 0 1

2017中国大学生程序设计竞赛-哈尔滨站-重现赛（感谢哈理工）