UVA-10382 Watering Grass

題意：有一個長方形草坪，長為l，寬為w，在它的水準中心線上可以安裝n個噴水器來為草坪澆水，每個噴水器能夠灌溉的範圍是以該噴水器為中心的半徑為r的圓。我們要灌溉整個草坪，問你最少需要的噴水器數。

題解：很明顯這是一個最小區間覆寫問題~~（老長時間不寫了，寫個blog記錄下）~~

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
struct node{
	double left;
	double right;
}a[10009];
double solve(double r,double w)
{
	double tmp=r*r-w*w/4;
	return sqrt(tmp);
}
bool cmp(node x,node y)
{
	return x.right>y.right;
}
int main()
{
	int n,cnt,ans;
	double x,r,l,w,en;
	while(~scanf("%d%lf%lf",&n,&l,&w))
	{
		cnt=0;ans=0;en=0;
		for(int i=1;i<=n;i++)
		{
			cin>>x>>r;
			if(2*r<w) continue;
			double tmp;
			tmp=solve(r,w);
			a[++cnt].left=x-tmp;
			a[cnt].right=x+tmp;
		}
		sort(a+1,a+1+cnt,cmp);
		while(en<l)
		{
			int i;
			for(i=1;i<=cnt;i++)
			{
				if(a[i].left<=en&&a[i].right>en)
				{
					en=a[i].right;
					ans++;
					break;
				}
			}
			if(i==cnt+1) break;
		}
		if(en<l)
			cout<<"-1"<<endl;
		else
			cout<<ans<<endl;
	}
	return 0;
}