| 比赛 |
?板子大赛 |
评测结果 |
AAAAAA |
| 题目名称 |
喷水装置 |
最终得分 |
100 |
| 用户昵称 |
exil |
运行时间 |
0.217 s |
| 代码语言 |
C++ |
内存使用 |
3.81 MiB |
| 提交时间 |
2026-01-17 13:25:30 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
double l;
double r;
};
vector<node> v;
bool cmp(node a,node b){
if(a.l!=b.l)return a.l<b.l;
else return a.r<b.r;
}
signed main(){
freopen("sprinkler.in","r",stdin);
freopen("sprinkler.out","w",stdout);
int t;
cin>>t;
while(t--){
int n;
double w,l;
cin>>n>>l>>w;
v.clear();
for(int i = 1;i<=n;i++){
double r,x;
cin>>x>>r;
if(r>=w/2){
double y=sqrt(r*r-(w/2)*(w/2));
v.push_back({max(x-y,0.0),min(x+y,l)});
}
}
int pan=0;
sort(v.begin(),v.end(),cmp);
//for(int i = 0;i<v.size();i++)cout<<v[i].l<<" "<<v[i].r<<endl;
if(v[0].l!=0){
cout<<-1<<endl;
continue;
}
int len=v.size();
int shang=0;
int ans=0;
for(double i = 0;i<=l;i){
int now=-1;
int ui=0;
for(int j = shang;j<=len;j++){
//cout<<i<<" "<<v[j].l<<" "<<v[j].r<<endl;
if(v[j].l<=i && v[j].r>=i){
if(ui<v[j].r){
ui=v[j].r;
now=j;
}
}
}
if(now==-1 && i<l){
//cout<<v[shang].l<<" "<<v[shang].r<<endl;
pan=1;
break;
}
ans++;
shang=now+1;
i=v[now].r+0.0001;
}
if(pan==1)cout<<-1<<endl;
else cout<<ans<<endl;
}
return 0;
}