算法学习之路|区间选点问题

一条海岸线，在海中有一些岛屿，要在岸上建一些雷达，每个雷达有一定的照射范围d，问至少要建造多少雷达才能覆盖所有岛屿
输入格式：
输入有多组数据，第一行d,n为雷达半径和海岛个数，接下来n行每行两个数，是每个岛屿坐标，输入0 0结束

输出格式：
输出雷达个数，无法覆盖就输出-1
输入样例：
3 2
1 2
-3 1
2 1
1 2
0 2
0 0
输出样例：
Case 1: 2
Case 2: 1
解题思路：把覆盖范围区间化，简化成区间选点问题，贪心，
思路不难，但是有一些坑。

#include<stdio.h>  
#include<stdlib.h>  
#include<math.h>   
struct island  
{  
    float left,right;  
}is[1010];  
int cmp(const void *a, const void *b)  
{  
    return (*(struct island*)a).left>(*(struct island*)b).left?1:-1;  
}  
int main()  
{  
    int n,d,num =1;  
    while(scanf("%d%d",&n,&d)!=EOF&&(n||d))  
    {  
        int x,y,flag=0;  
        for(int i=1;i<=n;i++)  
        {  
            scanf("%d%d",&x,&y);  
            if(y>d)  
            flag=1;  
            float dis;  
            dis=sqrt((float)(d*d-y*y));  
            is[i].left=(float)x-dis;  
            is[i].right=(float)x+dis;  
        }  
        qsort(is+1,n,sizeof(is[0]),cmp);  
        int sum=1;  
        float r;  
        r=is[1].right;  
        for(int i=2;i<=n;i++)  
        {  
            if(r>is[i].right)
            r=is[i].right;  
            else if(is[i].left>r) 
            {  
                sum++;  
                r=is[i].right;  
            }  
        }  
        if(flag)  
        printf("Case %d: -1\n",num++);  
        else  
        printf("Case %d: %d\n",num++,sum);  
    }  
    return 0;  
}