Boundary

Boundary

参考：2020牛客多校(第二场) B. Boundary (计算几何)

因为三点确定一个圆，其中原点是固定的，所以只用遍历另两个点就可以了。这样复杂度是(O(n^2))的。另外还要用一个 map 来保存所有的圆心，以此来统计相同的圆心的个数。

要注意的是判断三点一线的情况，这种情况是没有办法让三个点形成圆的

思维还需要再严谨一点，例如求三点共圆的时候要考虑到三点共线。

// Created by CAD on 2020/7/14.
#include <bits/stdc++.h>
#define fi first
#define se second
#define pdd pair<double,double>
using namespace std;

map<pdd,int> m;
pdd circle(vector<double> x,vector<double> y){
    double a[3],b[3],c[3];
    for(int i=1;i<=2;++i)
        a[i]=x[i+1]-x[1],b[i]=y[i+1]-y[1],c[i]=(a[i]*a[i]+b[i]*b[i])/2;
    double d=a[1]*b[2]-a[2]*b[1];
    double X,Y;
    X=x[1]+(c[1]*b[2]-c[2]*b[1])/d;
    Y=y[1]+(a[1]*c[2]-a[2]*c[1])/d;
    return {X,Y};
}
//求向量积
double fun(pdd a, pdd b){
    return a.fi*b.se-b.fi*a.se;
}

vector<pdd> p;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;++i){
        double x,y;cin>>x>>y;
        p.push_back({x,y});
    }
    if(n<=2){
        cout<<n<<endl;
        return 0;
    }
    int ans=0;
    double eps=1e-6;
    for(int ii=0;ii<n;++ii){
        pdd i=p[ii];
        m.clear();
        for(int jj=ii+1;jj<n;++jj){
            pdd j=p[jj];
            if(fabs(fun(i, j)) < eps) continue;	//排除三点共线的情况
            vector<double> x={0,0,i.fi,j.fi};
            vector<double> y={0,0,i.se,j.se};
            pdd d=circle(x,y);
            m[d]++;
            ans=max(ans,m[d]);
        }
    }
    cout<<ans+1<<endl;
    return 0;
}