UVa 10382喷水装置（降维处理后，再贪心）

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

请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？
分析：
对于此模型，我们不熟悉，熟悉的是在一条线上的处理，我们可以把此模型降维处理，变成一维的。对于一个圆的喷洒范围，可以看成看成上图中黄色的范围。，对于和长方形相切的圆，可以看成一个点，，没有覆盖范围。对于和长方形没有相交的圆，就不用考虑。
对于每一个黄色区间，按照左端点从小到大排序。每次都选择能往后延伸最长的那个区间。

代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,L,W;
struct node
{
    double l,r;
} s[15001];
int cmp(node t1,node t2)
{
    return t1.l<t2.l;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int k=0;/*有效圆的个数*/
        scanf("%d%d%d",&n,&L,&W);
        for(int i=0; i<n; i++)
        {
            int loca,rac;/*喷头的位置和浇灌半径*/
            scanf("%d%d",&loca,&rac);
            if(2*rac>W)
            {
                s[k].l=loca-sqrt(rac*rac-(W*W*1.0)/4);/*一个区间的左右端点*/
                s[k++].r=loca+sqrt(rac*rac-(W*W*1.0)/4);
            }
        }
        sort(s,s+k,cmp);
        if(s[0].l>0)/*左边的没有覆盖，可以直接输出*/
        {
            printf("-1\n");
            continue;
        }
        int book[15001];
        memset(book,0,sizeof(book));
        int flag,ans=0,t;
        double head=0,tail=0;
        while(1)
        {
            flag=0;
            for(int i=0; i<k; i++)/*每次就找一个区间，保证到右边最远*/
            {
                if(s[i].l<=head&&s[i].r>=tail&&book[i]==0)
                {
                    flag=1;
                    tail=s[i].r;
                    if(tail>=L)/*能把最右边覆盖*/
                        flag=2;
                    t=i;
                }
            }
            if(flag==1||flag==2)
            {
                book[t]=1;
                ans++;
                head=tail;
            }
            else
                break;
            if(flag==2)
                break;
        }
        if(tail<L)
            flag=0;
        if(flag==0)
            printf("-1\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}