1 solutions
-
1
#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