NYOJ 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

來源

《算法藝術與信息學競賽》

貪心解決問題

#include"stdio.h"
#include"math.h"
#include"stdlib.h"
#define N 100005
struct node
{
	double l,r;     //記錄每個水龍頭能灌溉的左右邊界
}f[N];
int cmp(const void*a,const void*b)
{
	return (*(struct node*)a).l<(*(struct node*)b).l?-1:1;
}          
int main()
{
	int t,n,i,j;
	double w,h,x,r;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%lf%lf",&n,&w,&h);
		h/=2;
		for(i=0,j=0;i0)
				break;
			if(rr=w)  
				break;
			if(f[i].l<=rr)     //從交叉地方取一個最右邊的那個噴水裝置
			{
				if(f[i].r>cur)
					cur=f[i].r;
			}
			if(f[i].l>rr)
			{
				if(f[i].l>cur)
				{
					cnt=0;
					break;
				}
				else
				{
					cnt++;
					rr=cur;
					cur=0;
				}
			}
		}
		if(rr