喷水装置

长L米，宽W米的草坪里装有n个浇灌喷头。每个喷头都装在草坪中心线上（离两边各W/2米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。

请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？

输入格式:
输入包含若干组测试数据。

第一行一个整数T表示数据组数。

每组数据的第一行是整数n、L和W的值，其中n≤10 000。

接下来的n行，每行包含两个整数，给出一个喷头的位置和浇灌半径。

如图1所示的示意图是样例输入的第一组数据所描述的情况。

输出格式:
对每组测试数据输出一个数字，表示要浇灌整块草坪所需喷头数目的最小值。如果所有喷头都打开还不能浇灌整块草坪，则输出-1。

输入样例:
3
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1
输出样例:
6
2
-1
数据范围与提示:
对于100%的数据，n≤15000。

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define N 15000

struct node
{
    double l,r;
}a[N];

int cmp(node a,node b)
{
	return a.l<b.l;
}

int main()
{
	int T,n;
	double L,W,pos,r;
    cin>>T;
    while(T--)
    {
        cin>>n>>L>>W;
        int num=0;
        while(n--)
        {
            cin>>pos>>r;
            if(r<=W/2)
                continue;
            a[num].l=pos-sqrt(r*r-(W/2)*(W/2));
            a[num++].r=pos+sqrt(r*r-(W/2)*(W/2));
        }
        sort(a,a+num,cmp);
        double s=0;//s表示目前覆盖区域
        int i=0,res=0;
        while(s<L)
        {
            res++;
            double t=s;
            for(;a[i].l<=t&&i<num;i++)
                if(a[i].r>s)
                    s=a[i].r;//寻找最大值
            if(t==s)//不变说明中断了
            {
                cout<<-1<<endl;
                break;
            }
        }
        if(s>=L)
            cout<<res<<endl;
    }
    return 0;
}