题目描述

假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。
每个小岛都位于海洋一侧的某个点上。雷达装置均位于海岸线上，且雷达的监测范围为 d，当小岛与某雷达的距离不超过 d
时，该小岛可以被雷达覆盖。我们使用笛卡尔坐标系，定义海岸线为 x轴，海的一侧在 x 轴上方，陆地一侧在 x轴下方。
现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。

输入格式
第一行输入两个整数 n
和 d，分别代表小岛数目和雷达检测范围。
接下来 n行，每行输入两个整数，分别代表小岛的 x，y轴坐标。
同一行数据之间用空格隔开。

输出格式
输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出 −1。

数据范围
1≤n≤1000

样例

输入样例：

3 2
1 2
-3 1
2 1

输出样例：

2

看看能覆盖此岛的雷达应该在的范围，然后进行区间选点。
给定若干个区间，最少选多少个点，可使每个区间上最少选一个点？？
贪心策略：

1. 将所有区间按右端点进行从小到大排序
2. 扫描每个线段
   情况一:如果选的上一个点不在此区间中，则选此区间的右端点。（因为是按照右端点升序排的序，所以选右端点更可能落在后面那个区间上，以达到最少选点个数）
   情况二:如果选的上一个点在此区间中，则跳过。

cnt：选了cnt个点说明存在cnt个互不相交的区间，cnt个互不相交的区间必须至少选cnt个点.
所有可行解>=cnt,因此cnt就是最少的选点个数

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
int n,d;
int x,y;
struct node{
    double l;
    double r;
    bool operator<(const node &x) const{
        return r<x.r;  
    }
}st[1005];
int main(int argc, char** argv) {
    scanf("%d%d",&n,&d);
    bool failed=false;
    for(int i=0;i<n;i++){
        scanf("%d%d",&x,&y);
        if(y>d) {
            failed=true;
        }
        else{
            double s=sqrt(d*d-y*y);
            st[i].l=x-s;
            st[i].r=x+s;
        }
    }
    sort(st,st+n);
    int cnt=0;
    double last=-1e20;//负无穷 
    for(int i=0;i<n;i++){
        if(last<st[i].l){
            last=st[i].r;
            cnt++;
        } 
    }
    if(failed==false){
    printf("%d\n",cnt);     
    }else{
        printf("-1\n");
    }
}