HDU 1883 Phone Cell（计算几何）

　　方法:选取一个点A,以点A为圆心做一个半径为r的圆,然后枚举另一个点B,以B为圆心做一个圆,如果这两个圆有交集,那我们在这个交集内选取一个点做半径为r的圆,这个圆就包括了A和B点,找到交集最多的区域并计算这个区域被覆盖的次数,把这个数加一就是最多能够覆盖的点个数,枚举所有的A,就可以得到最优解,剩下我想说的都在下面的图里,代码里也有相关注释;

　　这个题在比赛的时候我们并没有做出来,赛后看了题解才知道,由于作者的代码风格很好,所以不做修改,下面是作者的原博客地址:

http://www.cnblogs.com/CSGrandeur/archive/2012/09/10/2678682.html

　　下面这个图片有助于理解代码

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>

#include <algorithm>
using namespace std ;
const double eps = 1e-8;
const double PI = acos(-1.0) ;
int n ;
double r ;
struct point
{
    double x,y ;

} p[2010] ;
struct node
{
    double angle ;
    int flag ;
} q[5000] ;
int dcmp(double d)
{
    return d < -eps ? -1 : d > eps ;
}
bool cmp(const node &a,const node &b)///角度区间排序,区间上限永远在上;
{
    if(dcmp(a.angle-b.angle) == 0 ) return a.flag > b.flag ;

    return a.angle < b.angle ;
}
double Cal(double x)
{
    return x*x ;
}
double dist(const point &a,const point &b)
{
    return sqrt(Cal(a.x-b.x)+Cal(a.y-b.y)) ;
}

int main()
{
    while(~scanf("%d%lf",&n,&r))
    {
        if(n == 0) break ;
        for(int i = 0 ; i < n ; i++)
            scanf("%lf%lf",&p[i].x,&p[i].y) ;

        int ans = 0,m = 0;
        for(int i = 0 ; i < n ; i++)
        {
            m = 0 ;
            for(int j = 0 ; j < n ; j++)
            {
                if(i == j) continue ;
                double d = dist(p[i],p[j]) ;
                if(d > 2*r+0.001) continue ;
                double s = atan2(p[j].y-p[i].y,p[j].x-p[i].x) ;
                ///atan2 和 atan 的区别;
                ///1：参数的填写方式不同；
                ///2：atan2 的优点在于 如果 x2-x1等于0 依然可以计算，但是atan函数就会导致程序出错；
                if(s < 0) s += 2*PI ;///角度区间修正
                double ph = acos(d/2.0/r) ;///圆心角转区间
                q[m++].angle = s - ph + 2*PI ;///图中b-a,避免负值+2*PI;
                q[m-1].flag = 1 ;///标记为上界

                q[m++].angle = s + ph + 2*PI ;///图中a+b;
                q[m-1].flag = -1 ;///标记下界
            }
            sort(q,q+m,cmp) ;
            int sum = 0 ;
            for(int j = 0 ; j < m ; j++)///这种记录区间最大交集次数的方式很巧妙,当时我对这里还是挺困惑的,读者若不懂应稍加思考.
                ans = max(ans,sum += q[j].flag) ;
        }
        /*for(int j = 0; j < m; j++)
        {
            cout<<"angle = "<<q[j].angle<<endl;
            cout<<"flag = "<<q[j].flag<<endl;
        }*/
        printf("It is possible to cover %d points.
",ans+1) ;
    }
    return 0 ;
}