hihocoder [Offer收割]编程练习赛14 剑刃风暴

/*
可以证明最优的圆上至少有两个点（否则可以在不影响最优的情况下挪到满足条件） 
然后枚举其中一个点，用类似扫描线的方法统计，只不过这个区间变成了圆心到该点的方位角 时间复杂度是O(n2lgn)
*/
#include<cmath>
#include<cstdio>
#include<algorithm>
#define pf(x) ((x)*(x))
using namespace std;
typedef double real;
const int N=2e5+5;int n,r,dr;
struct Point{real x,y;}p[N];
struct node{real angle;bool in;}arc[N];
real dist(const Point &a,const Point &b){
    return sqrt(pf(a.x-b.x)+pf(a.y-b.y));
}
bool cmp(const node &a,const node &b){
    return a.angle!=b.angle?a.angle<b.angle:a.in>b.in;
}
void MaxCirleCover(){
    int ans=1;
    for(int i=1;i<=n;i++){
        int cnt=0;real len=0;
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            if((len=dist(p[i],p[j]))>dr) continue;
            real angle=atan2(p[i].y-p[j].y,p[i].x-p[j].x);
            real phi=acos(len/dr);
            arc[cnt].angle=angle-phi;arc[cnt++].in=true;
            arc[cnt].angle=angle+phi;arc[cnt++].in=false;
        }
        sort(arc,arc+cnt,cmp);
        int tmp=1;
        for(int i=0;i<cnt;i++){
            if(arc[i].in) tmp++;
            else tmp--;
            ans=max(ans,tmp);
        }
    }
    printf("%d\n",ans);
}
int main(){
    scanf("%d%d",&n,&r);dr=r*2;
    for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    MaxCirleCover();
    return 0;
}