10. 浇水系统
XJOI - 题目ID：9560选做题100分
最新提交：
Wrong Answer
83 分
历史最高：
Wrong Answer
83 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
题目描述：
长L米，宽 W 米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W/2 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。
请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？
输入格式：
输入包含若干组测试数据。
第一行一个整数 T 表示数据组数；
每组数据的第一行是整数n 、L 和 W；
接下来的 n 行，每行包含两个整数，给出一个喷头的位置和浇灌半径（上面的示意图是样例输入第一组数据所描述的情况）。
输出格式：
输出一个数字，表示要浇灌整块草坪所需喷头数目的最小值。如果所有喷头都打开也不能浇灌整块草坪，则输出“-1”。
样例输入：
3
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1
样例输出：
6
2
-1
约定：
n<=15000,
提示：
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct node{
double begin;
double end;
};
bool cmp(node x,node y){
return x.begin<y.begin;
}
void f(){
int n,h,w;
cin>>n>>h>>w;
int x,r;
node a[15005];
int cnt=0;
for(int i=1;i<=n;i++){
cin>>x>>r;
if(r<=w/2.0){
continue;
}
a[++cnt].begin=x-sqrt(r*r-(w/2.0)*(w/2.0));
a[cnt].end=x+sqrt(r*r-(w/2.0)*(w/2.0));
}
sort(a+1,a+cnt+1,cmp);
double last=1.0;
int sum=0;
for(int i=1;i<=cnt;i++){
bool flag=0;
double m=0;
for(int j=i;j<=cnt;j++){
if(last>=a[j].begin){
m=max(m,a[j].end);
flag=1;
}
}
if(flag==0){
cout<<"-1"<<endl;
return ;
}
sum++;
last=m;
if(last>=h){
cout<<sum<<endl;
return ;
}
}
cout<<sum<<endl;
}
int main(){
int t;
cin>>t;
while(t--){
f();
}
return 0;
}