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