# HDU 6242 Geometry Problem (随机数，几何) - henuzxy - CSDN博客

Problem Description
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 (Xi,Yi) on the two-dimensional plane. Your task is to find a point P and a real number R, such that for at least ?N2? 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≤105).

The following N lines describe the points. Each line contains two real numbers Xi and Yi (0≤|Xi|,|Yi|≤103) 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 XP,YP,R, where (XP,YP) is the coordinate of required point P. Three real numbers you output should satisfy 0≤|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 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

N的范围是1e5，所以枚举点是行不通的，因为3个点可以确定一个圆，所以我们只要每次随机三个点然后来确定一个圆，最后在判断这个圆是否可行。因为至少有一半的点是在圆上所以随机的次数是非常少的。对于小于5个点的要直接特判。

``````#include

using namespace std;
const int MAX = 100010;
const double eps = 1e-5;
typedef long long ll;
int N;
double R;
map mp;
map::iterator it;
string num_string(int num){
string res = "";
while(num > 0){
int lef = num % 10;
num /= 10;
res += ('0' + lef);
}
return res;
}
class Point{
public:
double x,y;
Point(double xx = 0,double yy =0){
x = xx,y = yy;
}
void setdate(){
scanf("%lf%lf",&x,&y);
}
}q[MAX];

bool IsLine(Point &A,Point &B){
if(abs(A.x - B.x) < eps)
return true;
return false;
}
bool IsRow(Point &A,Point &B){
if(abs(A.y - B.y) < eps)
return true;
return false;
}
bool Isok(Point &A){//判断这个点是否可行
int c = 0;
int TT = N/2;
if(N % 2 == 1)  TT++;
for(int i=1;i<=N;++i){
double dis = sqrt((q[i].x-A.x)*(q[i].x-A.x)+(q[i].y-A.y)*(q[i].y-A.y));
if(abs(dis-R) < eps)
c++;
if(c >= TT)
return true;
}
return false;
}
Point Getcir(Point A,Point B,Point C){//给予三个点，求圆心。
double a = 2*(B.x - A.x);
double b = 2*(B.y - A.y);
double c = (B.x*B.x+B.y*B.y) - (A.x*A.x+A.y*A.y);
double d = 2*(C.x-B.x);
double e = 2*(C.y-B.y);
double f = (C.x*C.x + C.y*C.y) - (B.x*B.x + B.y*B.y);
double x = (b*f-e*c)/(b*d-e*a);
double y = (d*c-a*f)/(b*d-e*a);
double r = sqrt((x-A.x)*(x-A.x) + (y-A.y)*(y-A.y));
Point ans(x,y);
R = r;
return ans;
}
void solve(){
if(N == 1){
printf("%.5lf %.5lf %.5lf\n",q.x+1,q.y,1.0);
}
else if(N == 2 || N == 3 || N == 4){
double xx = (q.x+q.x)/2;
double yy = (q.y+q.y)/2;
R = sqrt((q.x-xx)*(q.x-xx) + (q.y-yy)*(q.y-yy));
printf("%.5lf %.5lf %.5lf\n",xx,yy,R);
}
else{
while(true){
int p1 = rand() % (N+1),p2 = rand() % (N+1),p3 = rand() % (N+1);
if(p1 == p2 || p2 == p3 || p1 == p3)    continue;
//这部分是判断这三个点是否出现过，不过好像不判断更加快。
string ss = "";
ss += num_string(p1);ss += num_string(p2);ss += num_string(p3);
it = mp.find(ss);
if(it == mp.end())
mp[ss] = true;
else
continue;

Point A = q[p1],B = q[p2],C = q[p3];
//判断这三个点是否共线，如果共线要重新选取
if(IsLine(A,B) && IsLine(B,C))  continue;
if(IsRow(A,B) && IsRow(B,C))    continue;
Point res = Getcir(A,B,C);
if(Isok(res)){
printf("%.5lf %.5lf %.5lf\n",res.x,res.y,R);
break;
}
else
continue;
}
}
}
int main(void){
int T;
scanf("%d",&T);
while(T--){
srand(time(NULL));
mp.clear();
scanf("%d",&N);
for(int i=1;i<=N;++i)
q[i].setdate();
solve();
}
return 0;
}
``````

(注：此网站文章大都来自公开的博客，如有原作者发现有侵权问题，请在此留言，我们会立刻删除相关文章。)