题目地址：http://poj.org/problem?id=1328
/*
贪心
(转载)题意：有一条海岸线，在海岸线上方是大海，海中有一些岛屿，
这些岛的位置已知，海岸线上有雷达，雷达的覆盖半径知道，
问最少需要多少个雷达覆盖所有的岛屿。
(错误)思路：我开始是想从最左边的点雷达能探测的到的最右的位置出发，判断右边其余的点是否与该点距离小于d
是，岛屿数-1；不是，雷达数+1，继续。。。
(正确)思路：每个岛屿的座标已知，以雷达半径为半径画圆，与x轴有两个交点。
也就是说，若要覆盖该岛，雷达的位置范围是这两个交点。因此转化为覆盖区间的问题。
参考代码：http://www.cnblogs.com/kuangbin/archive/2011/07/30/2121838.html
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std; const int MAXN = 1e3 + ;
const int INF = 0x3f3f3f3f;
struct NODE
{
int x, y;
double l, r;
}node[MAXN]; bool cmp(NODE a, NODE b)
{
return a.l < b.l;
} bool ok(int n, int d)
{
if (d < ) return false;
for (int i=; i<=n; ++i)
{
if (node[i].y > d) return false;
} return true;
} void work(int n, int d)
{
int cnt = ;
double now = node[].r;
for (int i=; i<=n; ++i)
{
if (now > node[i].r) now = node[i].r;
if (now < node[i].l)
{
now = node[i].r;
cnt++;
}
}
printf ("%d\n", cnt);
} int main(void) //POJ 1328 Radar Installation
{
//freopen ("I.in", "r", stdin); int n, d;
int cnt = ;
while (~scanf ("%d%d", &n, &d) && n && d)
{
for (int i=; i<=n; ++i)
{
scanf ("%d%d", &node[i].x, &node[i].y);
node[i].l = (double)node[i].x - sqrt ((double)d * d - node[i].y * node[i].y);
node[i].r = (double)node[i].x + sqrt ((double)d * d - node[i].y * node[i].y);
}
sort (node+, node++n, cmp);
printf ("Case %d: ", ++cnt);
if (!ok (n, d))
{
printf ("%d\n", -); continue;
}
work (n, d);
} return ;
} /*
void work(int n, int d)
{
int i = 1;
int j = 1;
int next = 1;
int num = 0;
int cnt = 0;
while (num < n)
{
double res = node[i].x + sqrt (d * d - node[i].y * node[i].y);
cnt++; num++;
int flag = 0;
fors (j=i+1; j<=n; ++j)
{
if (pow (node[j].x - res, 2) + pow (node[j].y, 2) <= d * d)
{
num++; next = j; flag = 1;
}
}
if (flag) i = next + 1;
else i++;
}
printf ("%d\n", cnt);
}
*/