若有错误的地方,欢迎指正
题意
突然想想写这题的题解,发现老刘赛后没放出来….不过还好我有随手收藏题的习惯,当时截了图,原题如图所示(ps: 2018年注: 图丢了题意:给出n个点的坐标,问是否存在一个圆,满足n/3个点都在这个圆上;
题解
思路:显然,枚举三个点,找到一个圆,然后逐一验证是否满足题意的做法会超时。那么:
1.考虑优化枚举点的复杂度:假设存在满足题意的圆,那么1/3的点在这个圆上。由于三点确定一个圆,那么找到这个圆的概率为1/3 1/3 1/3;理论上,随机找三个点有1/27的概率找到这个圆,保险起见我们考虑找500次左右。
2.已知三个点的坐标求解圆的方程:推导详见此博客,简单的说是消参,对于局部式子设变量求解;
3.逐一验证剩余的点即可;
4.细节:对于浮点数,取绝对值用fabs;验证点到圆心的距离时,比较精度为1e5,根据提交情况进行调整即可;
相关算法
随机化
算是学习了一下,用起来很简单:
#include<cstdlib>
#inlcude<ctime>
using namespace std;
int main(){
srand(time(0));
int x=rand()%n+1;
return 0;
}
代码如下
亲测AC
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<ctime>
#include<cstdlib>
using namespace std;
double x[30001],y[30001];
int main(){
freopen("data.txt","r",stdin);
int T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
srand(time(0));
int flag=0;
for(int t=1;t<=500;t++){
int i=rand()%n+1;
int j=rand()%n+1;
int k=rand()%n+1;
double a=2*(x[j]-x[i]);
double b=2*(y[j]-y[i]);
double c=x[j]*x[j]+y[j]*y[j]-x[i]*x[i]-y[i]*y[i];
double d=2*(x[k]-x[j]);
double e=2*(y[k]-y[j]);
double f=x[k]*x[k]+y[k]*y[k]-x[j]*x[j]-y[j]*y[j];
double x0=(b*f-e*c)/(b*d-e*a);
double y0=(d*c-a*f)/(b*d-e*a);
double r=sqrt((x0-x[i])*(x0-x[i])+(y0-y[i])*(y0-y[i]));
int tot=0;
for(int i=1;i<=n;i++){
double d2=sqrt((x[i] - x0) * (x[i] - x0) + (y[i] - y0) * (y[i] - y0));
if(abs(d2 - r) <= 1e-5) tot++;
}
int judge=n/3;
if(judge<=tot){
flag=1;
break;
}
}
if(flag) printf("YOUGE\n"); else printf("NIUGE\n");
}
return 0;
}