1 solutions

  • 1
    @ 2024-12-7 18:22:32
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=15019;
    struct cir{
    	double l,r;
    }a[maxn];//即圆的有效覆盖范围 
    bool cmp(cir a,cir b){
    	return a.l<b.l;
    }//按左端点 
    double maxp(double a,double b){
    	if(a>=b)return a;
    	else return b;
    }
    int T,n,L,W;
    int main(){
    	cin>>T;
    	while(T--){
    		cin>>n>>L>>W;
    		for(int i=1;i<=n;i++){
    			int pos,r;
    			cin>>pos>>r;
    			a[i].l=a[i].r=0;
    			if(r>W/2.0){
    				double delta=sqrt(r*r-(W*W/4.0));
    				a[i].l=pos-delta;
    				a[i].r=pos+delta;
    			}
    		}
    		sort(a+1,a+n+1,cmp);
    		int i=1;
    		double b=0,e=0;
    		int cnt=0;
    		bool flag=0;
    		while(e<L){
    			cnt++;
    			b=e;
    			for(;a[i].l<=b&&i<=n;i++){
    				e=maxp(e,a[i].r);
    			}
    			if(b==e&&e<L){
    				cout<<-1<<'\n';
    				flag=1;
    				break;
    			}
    		}
    		if(!flag)cout<<cnt<<'\n';	
    	}
    	return /*164*/0;
    }
    
    
    • 1

    Information

    ID
    3
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    9
    Tags
    # Submissions
    15
    Accepted
    3
    Uploaded By