UVa 10382 - Watering Grass

　　题目大意：有一条长为l，宽为w的草坪，在草坪上有n个洒水器，给出洒水器的位置和洒水半径，求能浇灌全部草坪范围的洒水器的最小个数。

　　经典贪心问题：区间覆盖。用计算几何对洒水器的覆盖范围简单处理一下即可得到每个区间的范围，剩下的就是区间覆盖了。可参考UVa 10020 - Minimal coverage

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 #define MAXN 10000+10

 struct Interval

 {

     int pos, r;

     double s, e;

     bool operator < (const Interval& in) const

     {

         return s < in.s;

     }

 };

 Interval interval[MAXN];

 double cover(double c, double a)

 {

     return sqrt(c*c - a*a);

 }

 int main()

 {

 #ifdef LOCAL

     freopen("in", "r", stdin);

 #endif

     int n, l, w;

     while (scanf("%d%d%d", &n, &l, &w) != EOF)

     {

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

         {

             scanf("%d%d", &interval[i].pos, &interval[i].r);

             double t = cover(interval[i].r, w/2.0);

             interval[i].s = interval[i].pos - t;

             interval[i].e = interval[i].pos + t;

         }

         sort(interval, interval+n);

         double  start = ;

         int p = , ans = ;

         bool ok = true;

         while (start < l)

         {

             int q = p;

             double lmax = -;

             while (p < n && interval[p].s <= start)

             {

                 if (interval[p].e > lmax)   lmax = interval[p].e;

                 p++;

             }

             if (p == q || lmax <= start)

             {

                 ok = false;

                 break;

             }

             ans++;

             start = lmax;

         }

         if (ok)   printf("%d\n", ans);

         else   printf("-1\n");

     }

     return ;

 }