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中国大学生程序设计竞赛-哈尔滨站-重现赛（感谢哈理工） #### 题解 随机化 题意：给出一系列点，问一点P为圆心R为半径的圆，至少ceil(N/2)的点在圆上 思路：三点定圆,$($frac{1}{2})^3=$frac{1}{8}$的概率随机正确，当随机的次数够多(大约100次)正确率可以接近$99.99999999$% 注意特判4点与2点情况 #### 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.