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; 
}