原题链接

题解

1.将雷达建在海岸线上最优，覆盖的面积最大
2.根据光线可逆，雷达安装的位置覆盖多少小岛，等价于小岛被覆盖需要在哪个范围的位置上安装雷达
3.想象把雷达安装在最左边，然后慢慢往右移，这个时候雷达覆盖的小岛数量会越来越多，当右移到某个原本能覆盖的小岛覆盖不了时，在那个位置安装一个雷达
4.重复上述操作，我们发现就是把小岛需要安装雷达的范围按右端点排序，期间左端点大的就可以免安装

code

#include<bits/stdc++.h>
using namespace std;
struct node
{
    double x,y;
    double l,r;
};
int vis[1005]={0};
bool cmp(node a,node b)
{
    return a.r<b.r;
}
int main()
{
    node a[1005];
    int n;
    double d;
    cin>>n>>d;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
        double x=a[i].x,y=a[i].y;

        if(y>d){puts("-1");return 0;}
        double len=sqrt(d*d-y*y);
        a[i].l=x-len;
        a[i].r=x+len;
    }

    sort(a+1,a+n+1,cmp);

    int ans=0;
    for(int i=1;i<=n;i++)
    {
        //printf("now:%d, l:%lf  r:%lf\n",i,a[i].l,a[i].r);
        if(vis[i]) continue;
        vis[i]=1;
        ans++;
        for(int j=i+1;j<=n;j++)
        {
            if(a[j].l<=a[i].r) vis[j]=1;
            else break;
        }
    }

    cout<<ans<<endl;
    return 0;
}