雷达覆盖

Description

以雷达心为圆心的半圆形雷达覆盖范围有多个点 雷达可旋转，求最多覆盖数（含在边界的）

Input

Output

Sample Input

25 25 3.5－－－－－－雷达坐标与半径
7－－－－－－－－－－点数
25 28－－－－－－－点坐标
23 27
27 27
24 23
26 23
24 29
26 29
350 200 2.0
5
350 202
350 199
350 198
348 200
352 200
995 995 10.0
4
1000 1000
999 998
990 992
1000 999
100 100 -2.5

Sample Output

3
4
4

分析
先把在半径之外的点排除
枚举点作为雷达的分界线，用叉积判断左右两边点数量的多少，找一个最优值。

程序：

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
double r;
int sx,sy,n,nm,ans,x[10001],y[10001],w=0;
void work1();
int main()
{
    do
    {
        int j,k;
        cin>>sx>>sy>>r;
        if (r<0) break;
        cin>>n;
        nm=0;
        ans=0;
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        for (int i=1;i<=n;i++)
        {
            cin>>j>>k;
            if (sqrt((j-sx)*(j-sx)+(k-sy)*(k-sy))<=r)
            {
                nm++;
                x[nm]=j;
                y[nm]=k;
            }
        }
        int l,r,m;
        for (int i=1;i<=nm;i++)
        {
            l=0;
            r=0;
            for (int j=1;j<=nm;j++)
            {
                m=(x[i]-sx)*(y[j]-sy)-(y[i]-sy)*(x[j]-sx);
                if (m>0) r++;else l++;
            }
            if (l<r) l=r;
            if (l>ans) ans=l;
        }
        cout<<ans<<endl;    
    }while(w==0);
    return 0;
}