Geometry Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1091 Accepted Submission(s): 208
Special Judge
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.
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 Npoints are distinct.
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.
题意 给出n个点 确定一个圆的圆心和半径 使得至少n/2个点（向上取整）在该圆上 对于每组样例至少有一个解
解析 我们知道 在n个点中每个点在圆上的概率都为0.5 三个不共线的点确定一个外接圆 我们随机取三个点 这三个点的外接圆满足条件的概率为0.5*0.5*0.5=0.125
每次随机消耗的时间复杂度为1e5 枚举1秒内可以100 次 基本可以得到答案
AC代码
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
using namespace std;
const int maxn= 1e5+;
const double eps= 1e-;
const int inf = 0x3f3f3f3f;
typedef long long ll;
struct point
{
double x,y;
}a[maxn];
int n;
double dis(point a,point b) //两点间距离
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool waijie(point p1,point p2,point p3,point &ans) //引用修改圆心的值
{
if(fabs((p3.y-p2.y)*(p2.x-p1.x)-(p2.y-p1.y)*(p3.x-p2.x))<=eps)return false; //三点共线 没有外接圆
double Bx = p2.x - p1.x, By = p2.y - p1.y; //外接圆板子
double Cx = p3.x - p1.x, Cy = p3.y - p1.y;
double D = * (Bx * Cy - By * Cx);
double cx = (Cy * (Bx * Bx + By * By) - By * (Cx * Cx + Cy * Cy)) / D + p1.x;
double cy = (Bx * (Cx * Cx + Cy * Cy) - Cx * (Bx * Bx + By * By)) / D + p1.y;
ans.x=cx,ans.y=cy;
return true;
}
bool check(point mid,double d) //检查是否有n/2个点在外接圆上
{
int ans=;
for(int i=;i<=n;i++)
{
if(fabs(dis(a[i],mid)-d)<=eps)
ans++;
if((ans+(n-i))*<n) //简单优化一下 如果还未判断的点的数量加上已经满足条件的点的数量小于n/2 false
return false;
}
if(ans*>=n)
return true;
return false;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
if(n<=) //n小于等于4特判
{
printf("%lf %lf %lf\n",a[].x,a[].y,0.0);
continue;
}
else if(n<=)
{
printf("%lf %lf %lf\n",(a[].x+a[].x)/,(a[].y+a[].y)/,dis(a[],a[])/);
continue;
}
while(true)
{
point aa=a[rand()%n+],bb=a[rand()%n+],cc=a[rand()%n+]; //随机产生3个点
point xin;
if(!waijie(aa,bb,cc,xin))
continue;
double r=dis(aa,xin);
if(check(xin,r))
{
// printf("%lf %lf\n",aa.x,aa.y);
// printf("%lf %lf\n",bb.x,bb.y);
// printf("%lf %lf\n",cc.x,cc.y);
printf("%lf %lf %lf\n",xin.x,xin.y,r);
break;
}
}
}
return ;
}