| 比赛 |
?板子大赛 |
评测结果 |
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;
}