雷达设备

#include<cstring>
#include<string>
#include<iostream>
#include<vector>
#include<climits>
#include<math.h>
#include<algorithm>
#define ll long long
#define  pdd pair<double,double>
using namespace std;
const int N=1e6+10;
vector<pdd>a;
bool cmp (const pdd x,const pdd y)
{
    return x.second < y.second;
}
int main(){
    int n ;
    double m;
    cin >> n >> m;
    bool su = false ;
    for(int i = 0; i < n;i ++){
        double x, y;
        cin >> x >> y;
        if(y > m)su = true;
        a.push_back({x - sqrt(m * m - y * y), x + sqrt(m * m - y * y)});
    }
    if(su){
        puts("-1");
        return 0;
    }
    sort (a.begin(),a.end(),cmp);
    double r = a[0].second;
    int cnt = 1;
    for(int i = 1;i < a.size();i ++)
    {
        if(a[i].first <= r)
        {
            continue;
        }
        else {
            cnt ++;
            r = a[i].second;
        }
    }
    cout << cnt << endl;
    return 0;
}

本题考查的是贪心算法，每个小岛都有一个范围，在这个范围内，安装雷达可以检测到小岛。因此我们只需要将每个小岛的范围求出来，通过对右端点进行排序（当然对左端点进行排序也是可以的），如果第i个小岛的右端点在第i+1个小岛的左断点外，那么这两个小岛就可以共享一个雷达。