C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

贪心，脑筋急转弯

$图解：$

$贪心策略：$

$1、将所有区间按右端点排序$
$2、扫描每个线段$
$\ \ \ \ 1）：如果上一个点不在区间中，则选右端点$
$\ \ \ \ 2）：如果上一个点在区间中，则跳过$

$时间复杂度：O(nlogn)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1010;

int n, d;
struct Segment {
    double l, r;
    bool operator < (const Segment &t) const {
        return r < t.r;
    }
}seg[N];

int main() {
    cin >> n >> d;

    bool faild = false;
    for (int i = 0; i < n; i ++) {
        int x, y; cin >> x >> y;
        if (y > d) faild = true;
        else {
            double len = sqrt(d * d - y * y);
            seg[i] = {x - len, x + len};
        }
    }

    if (faild) {
        puts("-1");
    }
    else {
        sort(seg, seg + n);

        int cnt = 0;
        double last = -1e20;
        for (int i = 0; i < n; i ++)
            if (last < seg[i].l) {
                cnt ++;
                last = seg[i].r;
            }
        cout << cnt;    
    }

    return 0;
}