题目链接：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.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+yOfNvKO6PC9wPgo8cD48aW1nIHNyYz0="http://www.cppentry.com/upload_files/article/49/1_fh9ky__.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