【题目链接】:http://hihocoder.com/problemset/problem/1508

【题意】

【题解】



求一个半径为R的圆能够覆盖的平面上的n个点中最多的点数;

O(N2log2N)的复杂度;



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define Mn 2030//平面点集中点数

#define rep1(i,x,y) for (int i = x;i <= y;i++)

const double eps = 1e-9;//精度调高点没跑~

const double pi = acos(-1.0);

#define sqr(x) ((x) * (x))

struct point

{

    double x,y;

    double friend dis(const point &a,const point &b)

    {

       return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));

    }

}p[Mn + 5];

struct alpha

{

    double v;

    bool flag;

    bool friend operator <(const alpha &a,const alpha &b)//排序专用偏序关系

    {

       return a.v < b.v;

    }

}alp[Mn * Mn + 5];//C(N,2)*2的可能交点（可能极角）

int n;

double R;//半径

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    cin >> n >> R;

    rep1(i,1,n)

        cin >> p[i].x >> p[i].y;

    int MAX = 0;

    rep1(i,1,n)

    {

       int t = 0;

       rep1(j,1,n)

       {

           if(i == j)

              continue;

           double theta,phi,D;

           D = dis(p[i],p[j]);

           if(D > 2.0 * R)//距离超界直接秒杀

              continue;

//关键部分

           theta = atan2(p[j].y - p[i].y,p[j].x - p[i].x);

           if(theta < 0)

              theta += 2 * pi;

           phi = acos(D / (2.0 * R));

           t++;

           alp[t].v = theta - phi + 2 * pi;

           alp[t].flag = true;

           t++;

           alp[t].v = theta + phi + 2 * pi;

           alp[t].flag = false;

       }

       sort(alp+1,alp + 1 + t);

       int sum = 0;

       rep1(j,1,t)

       {

           if(alp[j].flag)

              sum ++;

           else

              sum --;

           if(sum > MAX)

              MAX = sum;

       }

    }

    printf("%d\n",MAX + 1);

    return 0;

}