【题解】雷达设备

贪心思路

1. 本题模型：区间选点 。
2. 以小岛为圆心，雷达扫描范围为半径，为每个小岛画一个圆。
3. 如果有小岛的圆与陆地没有交集，说明无法被扫描到。否则小岛 T 与陆地的交集所形成的区间 [l, r] 就是雷达可安置区间，将任意一枚雷达安置在区间 [l, r] 内，都可以扫描到小岛 T 。
4. 于是问题转化为求出每个小岛的雷达可安置区间，然后寻找最少需要多少个雷达可以覆盖所有区间。

关于实数

1. 由于本题计算区间涉及开方，所以雷达可安置区间的端点需要用实数。
2. 实数一般可以直接比较大小，但比较是否相等时最好用差值的形式比较（经测试本题直接比较是否相等也是可以的AC）。

c++ 贪心 16ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <map>
#include <unordered_map>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second

const int N = 100010, M = N * 2;

int n, d;
pair<double, double> p[N];

double get_c(int x, double y)
{
    return sqrt(x * x - y * y);
}

bool cmp(pair<double, double> a, pair<double, double> b)
{
    // 写成 if(a.y == b.y) 也可以过，但是由于实数自身存在误差，
    // 所以最好用差值的方式比较是否相等
    if (a.y - b.y < -1e6) return a.x < b.x;
    return a.y < b.y;
}

int main()
{
    cin >> n >> d;
    
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
    {
        int x, y;
        cin >> x >> y;
        if (y > d)
        {
            flag = false;
        }
        double c = get_c(d, y);
        p[i].x = x - c;
        p[i].y = x + c;
    }
    
    if (!flag)
    {
        cout << -1 << endl;
        return 0;
    }

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

    double l = -1e20;
    int ans = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (p[i].x > l)
        {
            ans ++ ;
            l = p[i].y;
        }
    }

    cout << ans;
    return 0;
}