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

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

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 #define MAXN 10000+10 6  7 struct Interval 8 { 9     int pos, r;10     double s, e;11     bool operator < (const Interval& in) const12     {13         return s < in.s;14     }15 };16 Interval interval[MAXN];17 18 double cover(double c, double a)19 {20     return sqrt(c*c - a*a);21 }22 23 int main()24 {25 #ifdef LOCAL26     freopen("in", "r", stdin);27 #endif28     int n, l, w;29     while (scanf("%d%d%d", &n, &l, &w) != EOF)30     {31         for (int i = 0; i < n; i++)32         {33             scanf("%d%d", &interval[i].pos, &interval[i].r);34             double t = cover(interval[i].r, w/2.0);35             interval[i].s = interval[i].pos - t;36             interval[i].e = interval[i].pos + t;37         }38         sort(interval, interval+n);39         double  start = 0;40         int p = 0, ans = 0; 41         bool ok = true;42         while (start < l)43         {44             int q = p;45             double lmax = -1;46             while (p < n && interval[p].s <= start)47             {48                 if (interval[p].e > lmax)   lmax = interval[p].e;49                 p++;50             }51             if (p == q || lmax <= start)52             {53                 ok = false;54                 break;55             }56             ans++;57             start = lmax;58         }59         if (ok)   printf("%d\n", ans);60         else   printf("-1\n");61     }62     return 0;63 }