本文共 1739 字，大约阅读时间需要 5 分钟。

描述

有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。

输入

第一行输入一个正整数N表示共有n次测试数据。

每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。

随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。

输出

每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。

如果不存在一种能够把整个草坪湿润的方案，请输出0。

样例输入

22 8 61 14 52 10 64 56 5

样例输出

12

思路：把覆盖面积问题转化为水平长度覆盖问题，如上图最后一个圆的红线就是该喷水装置可以覆盖的最大水平距离。

这题然后贪心：先按照起始位置从小到大排序，然后每次选择起点在当前覆盖范围内并且终点尽可能远的点，并更新覆盖距离。

如果发现 某一轮不能找到覆盖更远的点，说明不能完全覆盖。

#include
   
    using namespace std;struct Node{	double s,e;	bool operator<(const Node o)const{		return s < o.s;			}}nodes[10000+5];int t,n,w,h;int main()	{		scanf("%d",&t);		int x,r;		while(t--){			int cnt = 0;			scanf("%d%d%d",&n,&w,&h);			for(int i = 0; i < n; ++i){				scanf("%d%d",&x,&r);				if(r >= 1.0*h/2){					nodes[cnt].s = x-sqrt(r*r-1.0*h/2);					nodes[cnt].e = x+sqrt(r*r-1.0*h/2);					++cnt;				} 			}			sort(nodes,nodes+cnt);			bool flag = true;			double ma = 0,mi = w;			if(nodes[0].s > 0){				printf("0\n");				continue;			}			int ans = 0;			double cover = 0; //总的覆盖长度			int cur_max = 0;			while(cover < w){//进入循环则说明目前没有完全覆盖				cur_max = 0;//本轮最大覆盖长度 				for(int j = 0; j < cnt && nodes[j].s <= cover; ++j){//新的区间起点需要在当前覆盖的长度内					if(nodes[j].e-cover > cur_max){ //判断是否有更长的区间						cur_max = nodes[j].e-cover;					}				}				if(cur_max == 0){//本轮没有获得一个区间，说明没有起点在cover内并且终点在cover外更远的点，即不能实现完全覆盖					flag = false;					break;				} 				else{					++ans;					cover += cur_max; //更新当前覆盖的长度				}			}			if(!flag){				printf("0\n");				continue;			}			printf("%d\n",ans);			//			for(int i = 0; i < cnt; ++i){//				printf("%lf %lf\n",nodes[i].s,nodes[i].e);//			} 					}		return 0;	}