POJ - 1981 ：Circle and Points （圆的扫描线） hihocoder1508

题意：给定N个点，然后给定一个半径为R的圆，问这个圆最多覆盖多少个点。

思路：在圆弧上求扫描线。

如果N比较小，不难想到N^3的算法。 一般这种覆盖问题你可以假设有两个点在圆的边界上，那么每次产生的圆去看多少个点在园内即可。

但是我们现在要更高效的做法。题目等价于，有N个半径为R的圆，问二维平面上一点最多被多少个圆覆盖。即我们可以每次求交，交的部分标记++；

hihocoder1508的代码。

#include<bits/stdc++.h>

#define pdd pair<double,int>

#define f first

#define s second

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

const double eps=1e-;

const double pi=acos(-1.0);

struct point{ double x,y;}p[maxn];

double det(point a,point b){ return a.x*b.y-a.y*b.x;}

double dot(point a,point b){ return a.x*b.x+a.y*b.y;}

point operator +(point a,point b){ return point{a.x+b.x,a.y+b.y}; }

point operator -(point a,point b){ return point{a.x-b.x,a.y-b.y}; }

double dist(point a,point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

int dcmp(double x){ if(fabs(x)<eps) return ; return x>?:-;}

pdd a[maxn]; int ans,N; double ang1,ang2,R;

void CirinterCir(point a,point b)

{

    double L=dist(a,b)/,t=acos(L/R);

    double base=atan2(b.y-a.y,b.x-a.x);

    ang1=base+t,ang2=base-t;

}

bool check(point i,point j)

{

    double ang=(ang1+ang2)/;

    point x=point{i.x+R*cos(ang),i.y+R*sin(ang)};

    return dcmp(dist(x,j)-R)<=;

}

void solve()

{

    rep(i,,N) {

        int cnt=,Mx,tot=;

        rep(j,,N) {

            if(i==j||dist(p[i],p[j])>R+R) continue;

            if(p[i].x==p[j].x&&p[i].y==p[j].y) { cnt++; continue;}

            CirinterCir(p[i],p[j]);

            if(ang1>ang2) swap(ang1,ang2);

            if(check(p[i],p[j])){

                a[++tot]=pdd(ang1-eps,-);

                a[++tot]=pdd(ang2,);

            }

            else {

                a[+tot]=pdd(-pi-eps,-);

                a[++tot]=pdd(ang1,);

                a[++tot]=pdd(ang2-eps,-);

                a[++tot]=pdd(pi,);

            }

        }

        sort(a+,a+tot+); Mx=cnt;

        rep(i,,tot){

            if(a[i].s==-) cnt++;

            else cnt--;

            Mx=max(Mx,cnt);

        }

        ans=max(ans,Mx);

    }

}

int main()

{

    scanf("%d%lf",&N,&R);

    rep(i,,N) scanf("%lf%lf",&p[i].x,&p[i].y);

    solve();

    printf("%d\n",ans);

    return ;

}