HDU - 6242 Geometry Problem （幾何，思維，随機）

​​hdu - 6242 ​​

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 nn distinct points (xi,yi)(xi,yi) on the two-dimensional plane. your task is to find a point pp and a real number rr, such that for at least ⌈n2⌉⌈n2⌉ given points, their distance to point pp is equal to rr.

input

the first line is the number of test cases.

for each test case, the first line contains one positive number n(1≤n≤105)n(1≤n≤105).

the following nn lines describe the points. each line contains two real numbers xixiand yiyi (0≤|xi|,|yi|≤103)(0≤|xi|,|yi|≤103) indicating one give point. it's guaranteed that nn points are distinct.

output

for each test case, output a single line with three real numbers xp,yp,rxp,yp,r, where (xp,yp)(xp,yp) is the coordinate of required point pp. three real numbers you output should satisfy 0≤|xp|,|yp|,r≤1090≤|xp|,|yp|,r≤109.

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 rr if it is within an absolute error of 10−310−3 of rr.

sample input

sample output

給n個互補相同的二維坐标點，保證可以找到一個點\(p(x,y)\)，滿足存在\(ceil(n/2)\) 個點和這個點p的距離相同。

當n=1時，p可以為任意一點

當\(2<=n<=4\) 時，取任意兩點的中點即可，

當n>=5 時，

我們随機3個互補相同的點，并找到以這3個點确定的圓的圓心以及半徑r，然後計算有多少個點和這個圓心的距離為r，如果個數*2>=n，就說明該圓心就是要找的點，半徑就是距離。

為什麼這樣可以？

因為保證一定存在解，那麼一定有至少\(ceil(n/2)\) 個點在同一個圓上，那麼找到3個點都在這個圓上的機率大概就是\((1/2)^3\) 那麼期望大概就是8次就可以确定出圓心。