2. 浇水系统
题目ID：9560必做题100分
最新提交：
Wrong Answer
0 分
历史最高：
Wrong Answer
50 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
题目描述：
长L米，宽 W 米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W/2 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。
请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？
输入格式：
输入包含若干组测试数据。
第一行一个整数 T 表示数据组数；
每组数据的第一行是整数n 、L 和 W；
接下来的 n 行，每行包含两个整数，给出一个喷头的位置和浇灌半径（上面的示意图是样例输入第一组数据所描述的情况）。
输出格式：
输出一个数字，表示要浇灌整块草坪所需喷头数目的最小值。如果所有喷头都打开也不能浇灌整块草坪，则输出“-1”。
#include<bits/stdc++.h>
using namespace std;
int n,l,t,b1,b2,num,b3;
double cnt,w;
struct bg{
double l,r;
bool b;
}a[15010];
bool cmp(bg x,bg y){
return x.l<y.l;
}
int main(){
cin>>t;
for(int i=1;i<=t;i++){
num=0;
cin>>n>>l>>w;
cnt=l;
w/=2;
for(int j=1;j<=n;j++){
cin>>b1>>b2;
a[j].l=b1-sqrt(b2b2-ww);
a[j].r=b1+sqrt(b2b2-ww);
a[j].b=0;
}
sort(a+1,a+n+1,cmp);
b3=0;
while(cnt>0){
b3=0;
for(int j=1;j<=n;j++){
if(a[j].b==0&&a[j].r>=cnt){
b3=1;
num++;
cnt=a[j].l;
a[j].b=1;
break;
}
}
if(b3==0){
cout<<-1<<endl;
break;
}
}
if(b3==1)cout<<num<<endl;
}
return 0;
}
