C++ 代码

/*
 贪心:这道题类似于区间选点
 1.先计算出每个小岛能被雷达覆盖的最左和最右边界
 2.按照小岛能被覆盖的最右边界进行排序
 3.从前往后遍历每个区间,如果当前区间已经包含点了,直接pass掉
   否则选择当前区间的右端点(因为区间都在它的后边这样可以尽可能多的覆盖多的点)
*/   
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e3+10;
struct Node
{
    double l;
    double r;
}a[N];
bool cmp(Node a,Node b)
{
    return a.r<b.r;
}
int main()
{
    int n,d;
    scanf("%d%d",&n,&d);
    bool is_cover=false;
    for(int i=0;i<n;i++)
    {                                                                      
        int x,y;
        scanf("%d%d",&x,&y);
        if(y>d)
        {
            is_cover=true;
            break;
        }
        double len=sqrt(d*d-y*y);
        a[i].l=x-len,a[i].r=x+len;
    }
    sort(a,a+n,cmp);
    int ans=0;
    double point=-2e9;
    for(int i=0;i<n;i++)
    {
        if(a[i].l>point)
        {
            ans++;
            point=a[i].r;
        }
    }
    if(!is_cover) printf("%d\n",ans);
    else puts("-1");
    return 0;
}