bzoj1338: Pku1981 Circle and Points单位圆覆盖

传送门
首先，最有解一定是有一个点恰好在圆上。
然后我们枚举那个在圆上的点
然后我们计算出当圆心绕该店旋转时，其他点能被覆盖的区间
然后大力线段覆盖一发就行了
时间复杂度O（N^2logN)

#include<bits/stdc++.h>
using namespace std;
struct P{double x,y;}p[505];
struct data{
    double t; int f;
    bool operator <(const data &b)const{
        return t==b.t?f>b.f:t<b.t;
    }
}b[1005];
int n,ans,tot;
double dis(P a,P b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
    while (scanf("%d",&n)&&n){
        for (int i=0;i<n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        ans=1;
        for (int i=0;i<n;i++){
            tot=0;
            for (int j=0;j<n;j++){
                if (i==j) continue;
                if (dis(p[i],p[j])>2.0) continue;
                double x=atan2(p[i].y-p[j].y,p[i].x-p[j].x);
                double phi=acos(dis(p[i],p[j])/2);
                b[++tot]=(data){x-phi,1};
                b[++tot]=(data){x+phi,-1}; 
            }
            sort(b+1,b+tot+1);
            for (int i=1,tmp=1;i<=tot;i++)
                ans=max(ans,tmp+=b[i].f);
        }
        printf("%d\n",ans);
    }
}