POJ1328 Radar Installation贪心

题意：有一条海岸线，在海岸线上方是大海，海中有一些岛屿，这些岛的位置已知，海岸线上有雷达，雷达的覆盖半径知道，问最少需要多少个雷达覆盖所有的岛屿。
思路：每个岛屿的座标已知，以雷达半径为半径画圆，与x轴有两个交点。也就是说，若要覆盖该岛，雷达的位置范围是这两个交点。因此转化为覆盖区间的问题。
代码：
[cpp] 
#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <cmath> 
#include <string.h> 
using namespace std; 
 
const int N = 1010; 
struct point{ 
    int x,y; 
}pp[N]; 
struct line{ 
    double sp,ep; 
}ll[N]; 
bool cmp(line a,line b){ 
    if(a.ep == b.ep) 
        return a.sp < b.sp; 
    return a.ep < b.ep; 
}  www.2cto.com
int main(){ 
    //freopen("1.txt","r",stdin); 
    int n,len,ca = 1; 
    while(scanf("%d%d",&n,&len)){ 
        bool islen = false; 
        if(len < 0){ 
            islen = true; 
        } 
       if(n + len == 0 && len >= 0) 
           break; 
       bool flag = false; 
       for(int i = 0; i < n; ++i){ 
          scanf("%d%d",&pp[i].x,&pp[i].y); 
          if(pp[i].y > len) 
              flag = true; 
          double vx = sqrt((len * len - pp[i].y * pp[i].y)*1.0); 
          ll[i].sp = pp[i].x - vx; 
          ll[i].ep = pp[i].x + vx; 
       } 
       if(flag || islen){ 
         printf("Case %d: -1/n",ca++); 
         continue; 
       } 
       sort(ll,ll + n,cmp); 
       bool isuse[N]; 
       memset(isuse,false,sizeof(isuse)); 
       int ans = 0; 
       for(int i = 0; i < n; ++i){ 
           if(isuse[i]) 
               continue; 
           isuse[i] = true; 
           ans++; 
           for(int j = i + 1; j < n; ++j){ 
              if(isuse[j]) 
                  continue; 
              if(ll[j].sp <= ll[i].ep ){ 
                  isuse[j] = true; 
              } 
           } 
       } 
       printf("Case %d: %d/n",ca++,ans); 
    } 
    return 0; 
}