UVa 10382 喷水装置（贪心）

https://vjudge.net/problem/UVA-10382

题意：

有一个长为l，宽为w的草坪，在其中心线不同位置有n个点状的喷水装置，喷水坐标为p，喷水半径为r。求喷到所有草坪的最少喷水装置数量。

思路：

喷水装置的有效面积是图中的矩形部分，由此就把喷水区域变成了区间区域，之后利用贪心就可以了。

 #include<iostream>

 #include<string>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int maxn =  + ;

 int n;

 double l, w;

 struct node

 {

     double l, r;

 }a[maxn];

 double cacl(double y)

 {

     return sqrt(y*y - (w / 2.0)*(w / 2.0));

 }

 bool cmp(node a, node b)

 {

     return a.l < b.l;

 }

 int main()

 {

     ios::sync_with_stdio(false);

     //freopen("D:\\txt.txt", "r", stdin);

     double x, y;

     while (cin >> n >> l >> w)

     {

         int cnt = ;

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

         {

             cin >> x >> y;

             if (y <= w / 2.0)  continue;

             double m = cacl(y);

             a[cnt].l = x - m;

             a[cnt].r = x + m;

             cnt++;

         }

         sort(a, a + cnt, cmp);

         int num = ;

         int flag = ;

         double left = , right = ;

         if (a[].l <= )

         {

             int i = ;

             while (i < cnt)

             {

                 int j = i;

                 //找一个右端坐标最大的

                 while (j < cnt && a[j].l<=left)

                 {

                     if (a[j].r > right)

                     {

                         right = a[j].r;

                     }

                     j++;

                 }

                 if (i == j)  break;

                 i = j;

                 num++;

                 left = right;

                 if (left >= l)

                 {

                     flag = ;

                     break;

                 }

             }

         }

         if(flag) cout << num << endl;

         else cout << "-1" << endl;

     }

 }