uva--10382Watering Grass+貪心

uva--10382Watering Grass+貪心

題意：

一片長為L寬為W的矩形草坪，然後給出n個噴頭的圓心坐標和半徑，問你最少需要幾個噴頭可以覆蓋整個草坪。

思路：

剛開始的時候直接覺得可以算出每個噴頭可以覆蓋的區間，然後就變成前面剛做過的區間覆蓋問題了;後面看了一下樣例，發現這樣想是不對的，因為噴頭邊沿的圓弧可能是不能完全覆蓋住草地的，所以那些地方就必須還要別的噴頭去覆蓋，這樣就不能直接用區間合並來做了。後面又想了一下，其實每個噴頭覆蓋的有效區域就是一個矩形，我們只需要求出每個噴頭覆蓋的有效區域（就是矩形完全包含在圓內的部分，用簡單的幾何知識算一下就可以得到的），就又變成區間覆蓋問題了！有一點需要注意：如果一個噴頭的半徑不大於矩形寬度一半的話，那麼這個噴頭可以覆蓋的有效區域為0（相當於這個矩形的內接圓）,我們可以忽略這些噴頭。

代碼如下：

#include
#include
#include
#include
#include
using namespace std;

typedef struct
{
       double x,y;
}P;
P p[11000];

int cmp(P p1,P p2)
{
       return p1.xmax1)
                                  max1=p[i].y;
                              i++;
                      }
                      if(max1==0)
                          break;
                      cnt++;
                      left=max1;
                      if(left>=len)
                     {
                            flag=1;
                            break;
                     }
                }
                if(flag)
                     printf("%d\n",cnt);
                else
                     printf("-1\n");
       }
   return 0;
}