题目描述

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

思路

先用距离方程将肯定覆盖不了的点去掉，然后以每个点为边界用叉积求出左右两边的点数
注意边上的也算

#include <stdio.h>
#include <cmath>
#define maxn 800
int rx,ry;
double r;
struct arr
{
    int x,y;
}edge[maxn];
int find(int x,int y)
{
    double m=sqrt((x-rx)*(x-rx)+(y-ry)*(y-ry));
    if (m>r) return 0;
    else return 1;
}
int find1(arr a,arr b)
{
    return (b.x-rx)*(a.y-ry)-(a.x-rx)*(b.y-ry);
}
int main()
{

    while (~scanf("%d%d%lf",&rx,&ry,&r)&&r>0)
    {
        int n,l=0;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            edge[++l]=(arr){x,y};
            if (!find(x,y))
                l--;
        }

        int ans=0;
        for (int i=1;i<=l;i++)
        {
            int x=0,y=0;
            for (int j=1;j<=l;j++)
            {
                int t=find1(edge[i],edge[j]);
                if (t>=0) x++;
                else if (y<=0) y++;
            }
            if (ans<x) ans=x;
            if (ans<y) ans=y;
        }
        printf("%d\n",ans);
    }
}