比赛 ?板子大赛 评测结果 AAAAAA
题目名称 喷水装置 最终得分 100
用户昵称 2_16鸡扒拌面 运行时间 0.161 s
代码语言 C++ 内存使用 3.76 MiB
提交时间 2026-01-17 13:13:44
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

struct P {
    double l, r;
};

bool cmp(const P& a, const P& b) {
    return a.l < b.l;
}

int main() {
    freopen("sprinkler.in","r",stdin);
	freopen("sprinkler.out","w",stdout);
    int T;
    cin >> T;
    while (T--) {
        int n, L, W;
        cin >> n >> L >> W;
        vector<P> seg;
        for (int i = 0; i < n; i++) {
            int x, r;
            cin >> x >> r;
            
            if (2 * r <= W) continue;  // 不能覆盖整个宽度
            
            double d = sqrt(1.0 * r * r - 1.0 * (W / 2.0) * (W / 2.0));
            double l = x - d;
            double rp = x + d;
            
            if (rp < 0 || l > L) continue;  // 完全不覆盖草坪
            
            seg.push_back({max(0.0, l), min(1.0 * L, rp)});
        }
        
        sort(seg.begin(), seg.end(), cmp);
        
        double cov = 0.0;
        int cnt = 0;
        int idx = 0;
        bool ok = true;
        
        while (cov < L && ok) {
            double maxR = cov;
            bool found = 0;
            while (idx < seg.size() && seg[idx].l <= cov) {
                maxR = max(maxR, seg[idx].r);
                idx++;
                found = true;
            }
            
            if (!found) {
                ok = false;
                break;
            }
            
            cov = maxR;
            cnt++;
        }
        
        if (ok && cov >= L) {
            cout << cnt <<endl;
        } else {
            cout << -1<<endl;
        }
    }
    
    return 0;
}