题目链接：

http://poj.org/problem?id=1328

题意：

在x轴上有若干雷达，可以覆盖距离d以内的岛屿。

给定岛屿坐标，问至少需要多少个雷达才能将岛屿全部包含。

分析：

对于每个岛屿，计算出可以包含他的雷达所在的区间，找到能包含最多岛屿的区间即可。

可以看出这是一个典型的区间问题，我们有几种备选方法：

（1）优先选取右端点最大的区间。

（2）优先选取长度最长的区间。

（3）优先选取与其他区间重叠最少的区间。

2.3很容易想到反例，而1则是正确的，端点越靠右，剩下的区间就越少，需要的雷达就越少。

代码：

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

const int maxn = 1005, INF = 0x3f3f3f3f;

struct node

{

    double x, y;

    bool operator <(const node &a)const{

        return y > a.y;

    }

};

node p[maxn];

int main (void)

{

    int n, d;

    int Case = 1;

    while(scanf("%d%d", &n, &d) && (n != 0 ||d != 0)){

      int x, y;

      int maxy = -INF;

      for(int i = 0; i < n; i++)  {

            scanf("%d%d", &x, &y);

            maxy = max(maxy, y);

            double dis =  sqrt(1.0 * d * d  - 1.0 * y * y);

            p[i].x = 1.0 * x - dis;

            p[i].y = 1.0 * x + dis;

      }

      if(maxy > d || d < 0)  {

            printf("Case %d: -1\n", Case++);

            continue;

      }

      sort(p, p + n);

      int cnt = 1;

      double t = -INF;

      for(int i = 0; i < n; i++){

            if(t > p[i].y ) {

                cnt++;

                t = p[i].x;

            }

            else t = max(p[i].x, t);

        }

      printf("Case %d: %d\n", Case++, cnt);

    }

}