(HDU):6242 Geometry Problem (几何水题)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6242
Geometry Problem
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
题目大意
给出n个点,判断是否存在任意三个点组成的包含至少n/2个点的圆。
解题方法:
将所有点保存在一个集合里面,每次随机三个点看是否能够组成一个圆(三点共线则不成圆),如果能,则判断所有点是否有一半以上在所得的圆上即可。
三点共线判定:https://blog.csdn.net/sinat_38972110/article/details/82115637
此题数据不够严,不用用斜率来判断也能AC。
代码展示(可能有些不足):
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <cmath>
using namespace std;
const double eps=1e-3;
struct P
{
double x,y;
} sb[100005];
P Yuanxin(P a,P b,P c) //(已知三点求圆心坐标)
{
P q;
q.x=((c.y-a.y)*(c.y-b.y)*(b.y-a.y)+(a.x*a.x-b.x*b.x)*(c.y-a.y)-(a.x*a.x-c.x*c.x)*(b.y-a.y))/(2*((c.y-a.y)*(a.x-b.x)-(a.x-c.x)*(b.y-a.y)));
q.y=((c.x-a.x)*(c.x-b.x)*(b.x-a.x)+(a.y*a.y-b.y*b.y)*(c.x-a.x)-(a.y*a.y-c.y*c.y)*(b.x-a.x))/(2*((c.x-a.x)*(a.y-b.y)-(a.y-c.y)*(b.x-a.x)));
return q;
}
int main()
{
int t;
cin>>t;
srand((unsigned int)time(NULL));
/*
srand函数可以是每次随机的值不同(包含在 stdlib.h 头文件中)
*/
while(t--)
{
int n;
scanf("%d",&n);
for(int i = 0 ; i < n ; i++)
scanf("%lf%lf",&sb[i].x,&sb[i].y);
if(n == 1 || n == 2)
{
printf("%lf %lf %lf\n",sb[0].x + 1,sb[0].y,1.0);
continue;
}
if(n == 3 || n == 4)
{
printf("%lf %lf %lf\n",(sb[0].x+sb[1].x)/2,(sb[0].y+sb[1].y)/2,sqrt(((sb[0].x-sb[1].x)*(sb[0].x-sb[1].x))+((sb[0].y-sb[1].y)*(sb[0].y-sb[1].y)))/2);
continue;
}
while(1)
{
int a = rand()%n;
int b = rand()%n;
int c = rand()%n;
if(a == b || a == c || b == c)
continue;
double x1,x2,x3,y1,y2,y3;
x1=sb[a].x;x2=sb[b].x;x3=sb[c].x;
y1=sb[a].y;y2=sb[b].y;y3=sb[c].y;
if((x1 == x2 && x2 == x3) || (y1 == y2 && y2 == y3))
continue;
P yuanxin = Yuanxin(sb[a],sb[b],sb[c]);
double r = sqrt(((sb[a].x-yuanxin.x)*(sb[a].x-yuanxin.x))+((sb[a].y-yuanxin.y)*(sb[a].y-yuanxin.y)));
int sum=0;
for(int i = 0 ; i < n ; i++)
{
if(fabs(sqrt(((sb[i].x - yuanxin.x) * (sb[i].x - yuanxin.x)) + ((sb[i].y - yuanxin.y) * (sb[i].y - yuanxin.y))) - r) <= eps)
sum++;
}
if(2 * sum >= n)
{
printf("%lf %lf %lf\n",yuanxin.x,yuanxin.y,r);
break;
}
}
}
return 0;
}
上一篇: [OGR] 基础 1.4 Geometry几何属性
下一篇: POJ 2318 TOYS