POJ 1328 Radar Installation（貪心）

題目鏈接：http://poj.org/problem?id=1328

題目大意是在直線海岸線周圍有小島，建設雷達把小島覆蓋，但是雷達有直徑，要求建造最少的雷達。

很明顯就是一個貪心，就這題困了兩天；

剛開始我是打算，先按照X坐標以小到大，Y坐標以大到小排序，然後從最左上的小到開始，以每個小島為圓心，d(雷達半徑)為半徑畫圓，求出與海岸線交點然後以最右邊的交點建雷達，然後向右遍歷，如果在雷達范圍內的小島continue,否則在建，以此循環。就這樣死腦筋了好久，一直都不相信這樣是錯的。最後終於發現了漏洞。

如果有這樣的數據：

半徑d = 5

有兩個島嶼，坐標分別是：

X1 = -2，Y1 =4;

X2 = 0，Y2 = 5;

用我的思路就會像下圖的情況：

紅圈是島嶼以d為半徑畫的，此時，我的思路會把先建雷達1，然後判斷雷達1與小島2的距離判斷，發現不滿足，然後又建立了雷達2，最終結果的2個

但是只需要在原點建立雷達就足夠了，因此，這個思路是錯誤的。

我又重新構思了思路，我們可以以島嶼為圓心d為半徑得出在建雷達的陸地區間來，然後幾個島嶼疊加來獲得重復區間。

讓每個重復區間的島嶼盡量多，也就是讓每個雷達覆蓋盡量多的島嶼，這就是貪心所在。

還是這組數據，我們就得到這樣兩個區間，【-5,0】，【0，0】，然後疊加就是【0，0】；<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+yOfNvKO6PC9wPgo8cD48aW1nIHNyYz0="http://www.2cto.com/uploadfile/Collfiles/20140607/20140607091149387.jpg" alt="\">

藍色線就是第一個島嶼的區間，粉紅點就是雷達（疊加區間）所在。

因為這個疊加區間存在，所以一個雷達足以，反之，如果不存在，就需要新建雷達，並以最右的點再得區間。

這樣，代碼如下：

#include 
#include 
#include 
#include 

struct L
{
    double l,r;
}lim[10000];

int cmp(const void *a,const void *b)
{
    struct L *ta = (struct L *)a;
    struct L *tb = (struct L *)b;


    return ta->l > tb->l ? 1 : -1;
}

int main()
{
    int n,d;
    int i,k;
    int NO = 0;

    while (~scanf ("%d%d",&n,&d) && (n || d))
    {
        int tf = 0;

        for (i = 0; i < n;i++)
        {
            double x,y;
            scanf ("%lf%lf",&x,&y);
            if (y > d)
                tf = 1;

            lim[i].l = x - sqrt (d * d - y * y);
            lim[i].r = sqrt (d * d - y * y) + x;
        }

        if (tf)
        {
            printf ("Case %d: -1\n",++NO);
            continue;
        }

        qsort (lim,n,sizeof (lim[0]),cmp);
        int ans = 1;
        double s = lim[0].r;

        for (i = 1;i < n;i++)
        {
            if (lim[i].l > s)
            {
                s = lim[i].r;
                ans++;
            }else
            {
                s = s < lim[i].r ? s : lim[i].r;    //就因為這裡，WA了近10次
            }
        }

        printf ("Case %d: %d\n",++NO,ans);
    }
    return 0;
}

博客：http://blog.csdn.net/codehypo