# HDU 6242 Geometry Problem

/ 0评 / 0

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
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 $⌈\frac{N}{2}⌉$ given points, their distance to point $P$ is equal to $R$.

#### Input

The first line is the number of test cases.
For each test case, the first line contains one positive number $N(1≤N≤10^5)$.
The following $N$ lines describe the points. Each line contains two real numbers $X_i$ and $Y_i (0≤|X_i|,|Y_i|≤10^3)$indicating one give point. It's guaranteed that $N$ points are distinct.

#### Output

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≤|X_P|,|Y_P|,R≤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$.

#### #Source

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

• 默认
• 护眼
• 夜晚
• Serif
• Sans