2020牛客暑期多校训练营（第二场）B. Boundary

发表于 更新于 分类于

链接

https://ac.nowcoder.com/acm/contest/5667/B

题意

使n个点中尽可能多的点在某个圆上，这个圆过原点，求最多有多少个点

思路

枚举两个点，与原点构成三角形，求外接圆圆心（注意三点共线）

将所有圆心排序，计算相同的圆心个数的最大值 $y$

枚举求出 $C_x^2=y$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
const double eps=5e-7;
int sgn(double x) {return fabs(x)<eps?0:(x>0?1:-1);}
struct P {
    double x,y;
    P(){}
    P(double x,double y):x(x),y(y){}
    bool operator == (const P &a) const {return !sgn(x-a.x)&&!sgn(y-a.y);}
    bool operator < (const P &a) const {return sgn(x-a.x)<0||sgn(x-a.x)==0&&sgn(y-a.y)<0;}
    P operator + (const P &a) const {return P(x+a.x,y+a.y);}
    P operator - (const P &a) const {return P(x-a.x,y-a.y);}
    P operator * (const double &k) const {return P(x*k,y*k);}
    P operator / (const double &k) const {return P(x/k,y/k);}
    double operator ^ (const P &a) const {return x*a.y-y*a.x;}  //叉积
    P rotleft() {return P(-y,x);}  //绕原点逆时针旋转 90 度
}a[N],ps[N*N];
struct L {
    P s,t;
    L(){}
    L(P s,P t):s(s),t(t){}
    bool parallel(const L &a) {return sgn((t-s)^(a.t-a.s))==0;} //平行
    P cross_point(L a) { //两直线交点 需保证不平行不重合
        double t1=(t-s)^(a.t-a.s);
        double t2=(t-a.t)^(a.t-a.s);
        double l=(t1==0?0:t2/t1);
        P dd=P(t.x-(t.x-s.x)*l,t.y-(t.y-s.y)*l);
        return dd;
    }
};
P compute_circle_center(P a,P b,P c) {
    if(L(a,b).parallel(L(a,c))) return P(1e18,1e18);
    L u=L((a+b)/2,(a+b)/2+(b-a).rotleft());
    L v=L((a+c)/2,(a+c)/2+(c-a).rotleft());
    return u.cross_point(v);
}
int n,res,cnt;
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%lf%lf",&a[i].x,&a[i].y);
        for(int j=1;j<i;j++) {
            P t=compute_circle_center(P(0,0),a[i],a[j]);
            if(t.x==t.y&&fabs(t.x-1e18)<eps) continue;
            ps[++cnt]=t;
        }
    }
    if(cnt==0) res=1;
    else {
        sort(ps+1,ps+1+cnt);
        P pre=ps[1];
        int tot=1,mx=1;
        for(int i=2;i<=cnt;i++) {
            if(ps[i]==ps[i-1]) tot++,mx=max(mx,tot);
            else tot=1,pre=ps[i];
        }
        for(int i=n;i>=1;i--) if(i*(i-1)/2==mx) {res=i;break;}
    }
    printf("%d\n",res);
    return 0;
}