思路与算法

半径r大于W/2时，喷头在两条草坪边界可共同覆盖的横向区间为x±sqrt(r²-(W/2)²)。把问题化为覆盖[0,L]，反复选择左端不超过当前覆盖端、右端最远的区间。

正确性说明

草坪上固定横坐标的最远位置是两条边界，圆覆盖整个截面等价该横坐标落在所求区间。最左未覆盖位置必须由一个起点不晚于它的区间覆盖；把任意最优方案首个区间替成最远延伸者不会增加所需数量，递归得贪心最优。

复杂度

每组O(n log n)时间、O(n)空间，含区间构造、排序与线性扫描。

易错点

2r<=W不能覆盖正长度截面；边界相接可以接续，覆盖不前进即无解。几何运算使用long double并仅在端点比较给予微小舍入容差。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DS {
    vector<int> p, s;
    DS(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        return true;
    }
};

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        long double L, W;
        cin >> n >> L >> W;
        vector<pair<long double, long double>> a;
        while (n--) {
            long double x, r;
            cin >> x >> r;
            if (2 * r <= W)
                continue;
            long double z = sqrtl(r * r - W * W / 4);
            a.push_back({x - z, x + z});
        }
        sort(a.begin(), a.end());
        long double cur = 0;
        int i = 0, ans = 0;
        bool ok = true;
        while (cur < L) {
            long double far = cur;
            while (i < (int)a.size() && a[i].first <= cur + 1e-12L) {
                far = max(far, a[i].second);
                i++;
            }
            if (far <= cur) {
                ok = false;
                break;
            }
            cur = far;
            ans++;
        }
        cout << (ok ? ans : -1) << "\n";
    }
}