12.喷水装置（二）

• 描述

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

  • 输入

  • 第一行输入一个正整数N表示共有n次测试数据。
    每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。
    随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。

  • 输出

  • 每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。
    如果不存在一种能够把整个草坪湿润的方案，请输出0。

  • 样例输入

  • 2
    2 8 6
    1 1
    4 5
    2 10 6
    4 5
    6 5

  • 样例输出

  • 1
    2

//	12	4	喷水装置（二）
#include <stdio.h>
#include <math.h>
int main()
{
	int n1,n,w,h,x[10000],r[10000];
	int i,j,k,temp,result;
	double xx,max;
	scanf("%d",&n1);
	getchar();
	while(n1--)
	{
		scanf("%d%d%d",&n,&w,&h);
		getchar();
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&x[i],&r[i]);
			getchar();
		}
		
		//对所有喷水装置按坐标位置由近到远排序
		for(i=0;i<n-1;i++)
		{
			k=i;
			for(j=i+1;j<n;j++)
			{
				if(x[j]<x[k])
					k=j;
			}
			if(k!=i)
			{
				temp=x[i];
				x[i]=x[k];
				x[k]=temp;
				temp=r[i];
				r[i]=r[k];
				r[k]=temp;
			}
		}
		
		//计算最少使用多少喷水装置
		xx=0;
		result=0;
		k=-1;
	    while(xx<w)
		{
			for(i=k+1,max=0;i<n;i++)
			{
				if( (r[i]*r[i])-(h*h/4)>=((x[i]-xx)*(x[i]-xx)) && (x[i]+sqrt(r[i]*r[i]-h*h/4))>max )
				{
					max=x[i]+sqrt(r[i]*r[i]-h*h/4);
					k=i;
				}
			}
			xx=max;
			result++;
			if(0==xx)
			{
				result=0;
				break;
			}
		}
		printf("%d\n",result);
		
	}
	return 0;
}

原文：http://anglecode.blog.51cto.com/5628271/1617859