【正经题解】Gold King大范围洒洒

这道题目的主要思路如下：
对每个喷水装置按照其横坐标排序，同时如果两个装置横坐标相同，则将半径大的放在前面。
遍历排序后的喷水装置，如果当前装置的半径大于等于草坪的高度 h，则该装置能够完全润湿一列。将该装置的左右边界加入备选边界。
按照备选边界的左边界进行升序排序，然后使用贪心策略选择最少的喷水装置，使得草坪被完全覆盖。

#include<bits/stdc++.h>
using namespace std;

// 定义喷水装置的结构体
struct Sprinkler {
    double left, right; // 喷水装置的左右边界
};

// 自定义比较函数，用于排序喷水装置
bool compareSprinkler(const Sprinkler& a, const Sprinkler& b) {
    return a.left < b.left || (a.left == b.left && a.right > b.right);
}

// 冒泡排序，用于对喷水装置按照左边界进行排序
void bubbleSort(int l, int r, Sprinkler sprinklers[]) {
    for (int i = 0; i <= r; i++) {
        for (int j = i + 1; j <= r; j++) {
            if (sprinklers[i].left > sprinklers[j].left || 
               (sprinklers[i].left == sprinklers[j].left && sprinklers[i].right < sprinklers[j].right)) {
                swap(sprinklers[i], sprinklers[j]);
            }
        }
    }
}

int main() {
    int m;
    cin >> m;

    while (m--) {
        int sum = 0, index = 0;
        double x, r, n, w, h;
        cin >> n >> w >> h;

        Sprinkler sprinklers[10001];

        // 读入喷水装置的坐标和半径，筛选符合条件的喷水装置
        for (int j = 0; j < n; j++) {
            cin >> x >> r;
            if (2 * r > h) {
                double xr = sqrt(r * r - h * h / 4);
                sprinklers[index] = {max(0.0, x - xr), x + xr};
                index++;
            }
        }

        // 使用自定义的排序函数对喷水装置进行排序
        bubbleSort(0, index - 1, sprinklers);

        double begin = sprinklers[0].left, end = sprinklers[0].right;
        if (begin <= 0) sum++;
        
        int k = 1;
        while (k < index && sprinklers[0].left <= 0) {
            if (end >= w) break;
            if (k == index - 1) {
                sum++;
                end = sprinklers[index - 1].right;
                break;
            }
            if (end < sprinklers[k].left) break;
            
            double maxEnd = end;
            while (end >= sprinklers[k].left) {
                maxEnd = max(maxEnd, sprinklers[k].right);
                k++;
            }
            end = maxEnd;
            sum++;
        }

        if (end < w) sum = 0;

        cout << sum << endl;
    }

    return 0;
}