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$.

#### Sample Input

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


#### Sample Output

0 0 1


#### #Source

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

#### Code

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
#define clr(a,b) memset(a,b,sizeof(a))
const double eps = 1e-8;
const int maxn = int(1e5+7);
struct node {
double x,y;
node():x(0),y(0){}
node(double x,double y):x(x),y(y){}
node(const node &o){
x = o.x;
y = o.y;
}
}p[maxn];
struct circle {
node o; double r;
circle(node o, double r):o(o),r(r){}
};
double getDis(node &a, node &b) {
return hypot(fabs(a.x - b.x), fabs(a.y - b.y));
}
circle getCircumcircle(node a,node b,node c) { //返回三点的外接圆
double x1 = a.x, x2 = b.x, x3 = c.x;
double y1 = a.y, y2 = b.y, y3 = c.y;
double x0 = ((y2 - y1) * (y3 * y3 - y1 * y1 + x3 * x3 - x1 * x1) -
(y3 - y1) * (y2 * y2 - y1 * y1 + x2 * x2 - x1 * x1)) /
(2.0 * ((x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1)));
double y0 = ((x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1) -
(x3 - x1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1)) /
(2.0 * ((y3 - y1) * (x2 - x1) - (y2 - y1) * (x3 - x1)));
node o = node(x0, y0);
double r = getDis(a, o);
return circle(o, r);
}
inline bool judge(circle a, node b) {//判断点b是否在圆a上
return fabs(getDis(a.o, b) - a.r) < eps;
}
int cnt[maxn];
int main() {
int t; scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lf%lf", &p[i].x, &p[i].y);
cnt[i] = i;
}
if (n == 1) {
printf("%.6f %.6f %.6f\n", p[1].x, p[1].y, double(0));
continue;
}
if (n < 5) { //一定有解,两点定圆
printf("%.6f %.6f %.6f\n", (p[1].x + p[2].x) / 2,
(p[1].y + p[2].y) / 2,
getDis(p[1], p[2]) / 2
);
continue;
}
while (1) {
random_shuffle(cnt + 1, cnt + n + 1);
circle now = getCircumcircle(p[cnt[1]], p[cnt[2]], p[cnt[3]]);
int ans = 0;
for (int i = 1; i <= n; i++)
if (judge(now, p[i])) ans++;
if (ans >= (n + 1) / 2) {
printf("%.6f %.6f %.6f\n", now.o.x, now.o.y, now.r);
break;
}
}
}
return 0;
}


This site uses Akismet to reduce spam. Learn how your comment data is processed.