2016多校前的热身赛 1002 Circle Problem

若有错误的地方,欢迎指正

题意

突然想想写这题的题解,发现老刘赛后没放出来….不过还好我有随手收藏题的习惯,当时截了图,原题如图所示(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;
}