贪心：区间覆盖(Source: UVa 10382)

思路：转化成一维的形式(在代码中有注释)

 代码：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;

const int N=15010;

struct node
{
	double l,r;
	bool operator<(node t)//重载  
	{
		return l<t.l;
	}
}p[N];

void solve()
{
	int n,L,W;
	memset(p,0,sizeof p);
	cin>>n>>L>>W;
	int x,r;
	for(int i=0;i<n;i++)
	{
		cin>>x>>r;
		if(r<=W/2.0)
			continue;
		double t=sqrt(1.0*r*r-1.0*W*W/4.0);
		p[i].l=max(x-t,(double)0);
		p[i].r=x+t;
	}
	sort(p,p+n);//按左端点排序  
	int ans=0;
	double st=0;
	for(int i=0;i<n;i++)
	{
		int j=i;
		double r=-2e9;
		
		//找出左端点比r小的，且右端点比r大的最大值  
		while(j<n&&p[j].l<=st)
		{
			r=max(r,p[j].r);
			j++;
		}
		if(r<st)//表示有未覆盖到的地方 
		{
			cout<<-1<<endl;
			return;
		}
		ans++;
		if(r>=L)//已经全部覆盖  
			return;
		i=j-1;
		st=r;//更新覆盖到的最右边  
	}
	cout<<ans<<endl;
}


int main()
{
	int t;
	cin>>t;
	while(t--)
		solve();
	
	return 0;
}