南阳OJ-12-喷水装置（二）贪心+区间覆盖

题目链接：

http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=12

题目大意：

有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。

传送门：喷水装置（一）

思路：

区间覆盖问题，每个点有一段喷水区间，按照左端点排序即可，设置两变量begin， end，依次扫过去，每次取覆盖begin的区间更新end，如果没能覆盖begin，说明已经到了当前的最右端，begin=end，再次扫描，如果每次扫描开始的时候就不能覆盖begin，则无解，如果每次扫描的时候没有找到合适的end，也无解。如果最终的begin<l也表示到达不了终点。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int maxn = 1e4 + ;

 int T, n;double l, w;

 struct node

 {

     double x, y;

     bool operator < (const node a)const

     {

         return x < a.x;

     }

     node(){}

     node(double x, double y):x(x), y(y){}

 };

 node a[maxn];

 int main()

 {

     cin >> T;

     while(T--)

     {

         cin >> n >> l >> w;

         w = w * 0.5;

         int tot = ;

         double x, r;

         for(int i = ; i < n; i++)

         {

             cin >> x >> r;

             if(r <= w)continue;

             double c = sqrt(1.0 * r * r - w * w);

             a[tot].x = 1.0 * x - c;

             a[tot++].y = 1.0 * x + c;

             if(a[tot - ].x > l || a[tot - ].y < )tot--;

         }

         sort(a, a + tot);

         double begin = , end = -;

         int ans = ;

         for(int i = ; i < tot && begin < l;)

         {

             if(a[i].x > begin)

             {

                 ans = ;

                 break;

             }

             while(i < tot && a[i].x <= begin)//覆盖begin的区间更新出最大的end

             {

                 end = max(end, a[i].y);

                 i++;

             }

             if(end < )//说明没有找到合适的区间，直接无解

             {

                 ans = ;

                 break;

             }

             ans++;

             begin = end;//更新两者

             end = -;

         }

         if(begin < l)ans = ;

         cout<<ans<<endl;

     }

     return ;

 }