#10002. 「一本通 1.1 例 3」喷水装置（贪心区间覆盖问题）

喷水装置

题目描述：

长 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

数据范围与提示：

对于100%的数据n<=15000

每一个喷水装置能覆盖的最大范围
利用勾股定理！！！

当半径小于或者等于w/2的时候，如图所示，肯定不能全覆盖！！！

AC代码：

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int n,L,w,x,r,cnt;
struct note
{
	double x,y;	//储存一个喷水装置的左端点(x)和右端点(y)
} a[15010];
bool cmp(note x,note y)
{
	return x.x<y.x;//把该喷水装置的左端点进行从小到大排序
}//因为我们要按照从左到右的顺序进行全覆盖
void read()
{
	int i;
	cnt=1;
	scanf("%d%d%d",&n,&L,&w);
	for(i=1; i<=n; i++)
	{
		scanf("%d%d",&x,&r);
		if(r>w/2)//如果该喷水装置(图中的圆) 的上下边界小于或者等于草坪
		{
			//可以看图(即小于或者等于肯定不能做到全覆盖)
			a[cnt].x=x-sqrt(r*r-w*w/4.0);
			a[cnt].y=x+sqrt(r*r-w*w/4.0);
			cnt++;
		}
	}
}
void solve()
{
	double s,t=0;//s是当前覆盖的右端点，t是我们需要找到的右端点
	int ans=0;//ans是我们最后需要输出的最小值
	int i=1;
	while(t<L)//当t<L时意味着我们还没有全覆盖，所以要进行寻找
	{
		s=t;//找到t时我们就要把s==t
		for(; a[i].x<=s&&i<=cnt; i++)
		{
			if(a[i].y>t)//找右端点,注意在这里只能a[i].y>t而不能a[i].y>=t
				t=a[i].y;//当等于t的时候，t=a[i].y的值就不改变
		}//所以进行if(s==t)时，不管后面是否有符合覆盖条件的，都不会再去看，因为t的值没有改变
		if(s==t)
		{
			printf("-1\n");
			break;
		}
		ans++;
	}
	if(t>=L)
		printf("%d\n",ans);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		read();
		sort(a+1,a+1+cnt,cmp);//简单的sort排序
		solve();
	}
	return 0;
}