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;
}