POJ 1106 Transmitters（离散化）

题目链接：Click here~~

题意：

给你一个点的坐标和半径，然后给平面上的点集S，求以这个点为圆心的半圆最多能覆盖S中的点的个数。

解题思路：

首先，只有圆内或圆上的点才有可能被覆盖，所以先预处理将圆外的点全部舍弃。

然后，直观的想法是枚举每个角度，然后计算符合条件的点的个数。但是这种想法是无法实现的，因为你无法确定每次要旋转多少度。

接着，引入 离散化 的思想：最优解一定可以保证至少有一个点在直径上。

可以通过反证法进行证明：若没有点在直径上，通过顺时针(或逆时针)旋转一个角，使得至少有一个点在直径上，得到的结果一定不会更差。

如此，便可根据此性质，通过枚举每个可能在直径上的点，从而在O(n)内枚举出所有的角度（这里指有用的角度）。

然后，对于每个角度，可以再在O(n)内暴力找出所有在这条直径左手边（或右手边，下面以左手边为例）的点，更新最大值。

那么，还用不用考虑这条直径右手边的点了呢？

假设当前枚举到的点是A，则对于这条直径，只有两种情况：

1、点B存在。

那么，当枚举到点B的时候，可以考虑到直径下面的情况。

2、点B不存在。

那么，当直径逆时针旋转到与D相交时，得到的结果不会更差。

因为从OB到OD旋转的这段角度内下半部分的扇形没有点存在，而与其对应的上半部分有可能已经覆盖到了其他的点，所以覆盖的点只可能增加。

即这种情况下，当枚举到点D的时候，可以得到不会更差的解。所以可以忽略掉这种情况。

所以，每次就不用考虑直径右手边点的情况了。

#include <math.h>
#include <stdio.h>
#include <algorithm>
using namespace std;

#define N 155

const double eps = 1e-6;

struct Point
{
    int x,y;
}P[N],R,p;

double Dis(const Point& p1,const Point& p2)
{
    return sqrt( 1.0*(p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) );
}

double Cross(const Point& p1,const Point& p2,const Point& p3,const Point& p4)
{
    return (p2.x-p1.x)*(p4.y-p3.y) - (p2.y-p1.y)*(p4.x-p3.x);
}

bool InCir(const Point& p,const Point& R,double r)
{
    return Dis(p,R) <= r;
}

int main()
{
    int n,nn,ans;
    double r;
    while(~scanf("%d%d%lf",&R.x,&R.y,&r),r>=0)
    {
        n = ans = 0;
        scanf("%d",&nn);
        while(nn--)
        {
            scanf("%d%d",&p.x,&p.y);
            if(InCir(p,R,r))
                P[n++] = p;
        }
        for(int i=0;i<n;i++)
        {
            int tmp = 0;
            for(int j=0;j<n;j++)
                if(Cross(R,P[i],R,P[j]) >= 0)
                    ++tmp;
            ans = max(ans,tmp);
        }
        printf("%d\n",ans);
    }
    return 0;
}