贪心

贪心思路

我们把所有岛屿从左到右按x排序，从第一个岛屿开始，求出每一个岛屿对应的雷达可以安放的区间，看这个区间和之前的区间是否有交集，如果有就将这个区间和之前求交集，没有就应该新开一个雷达，而且这个雷达从这个没有交集的岛屿开始。

贪心原理

因为题目要求我们一定要将所有岛屿都覆盖在雷达范围内，所以要让一个雷达覆盖的范围尽可能多，从最左边开始，尽可能的让雷达覆盖更多岛屿，覆盖不了就新开雷达。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e3+7;
int n, idx, ans, d;

struct island{
    int x, y;
    bool operator <(const island b){
        return x < b.x;
    }
}a[N];

void getrange(double &l, double &r, int x, int y){
    double w = sqrt(d * d - y * y);
    l = x - w, r = x + w;
    return;
}

bool merge(double &l, double &r, double ll, double rr){
    ll = max(l, ll);
    rr = min(r, rr);
    if(ll > rr) return false;
    l = ll, r = rr;
    return true;
}

void solve()
{
    cin >> n >> d;
    bool f = true;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i].x >> a[i].y;
        if(a[i].y > d) f = false;
    }
    if(!f){
        cout << "-1\n";
        return;
    }
    sort(a + 1, a + 1 + n);
    int st = 1, ed;
    while(st <= n){
        double l = -N, r = N, ll, rr;
        for(ed = st; ed <= n; ed ++){
            getrange(ll, rr, a[ed].x, a[ed].y);
            if(!merge(l, r, ll, rr)) break;
        }
        ans ++;
        st = ed;
    }
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt --) solve();
    return 0;
}