浇水系统
总结
fad
时间限制: 1000ms
空间限制: 524288kB
长L米，宽 W 米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W/2 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。
请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？
https://xinyoudui.com/ac/contest/747003D6200053401A3D3F6/problem/6927
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,cnt,l,h,t,r,T,w;
struct node{
double x,y;
}a[20005];
bool cmp(node q,node h){
return q.x<h.x;
}
void pd(){
cin>>n>>l>>h;
cnt=0;
for(int i=1;i<=n;i++){
cin>>w>>r;
if(r<=h/2) continue;
cnt++;
a[cnt].x=w-sqrt(r*r-h*h/4.0);
a[cnt].y=w+sqrt(r*r-h*h/4.0);
}
}
void solve(){
double t=0;
int ans=0,bj=1,i=1;
while(t<l){
ans++;
double s=t;
for(;a[i].x<=s&&i<=cnt;i++)
if(t<a[i].y)
t=a[i].y;
if(t==s&&s<l){
cout<<-1<<"\n";
bj=0;
break;
}
}
if(bj) cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
pd();
sort(a+1,a+1+n,cmp);
solve();
}
}