一、内容
假定海岸线是无限长的直线。陆地位于海岸线的一侧，海洋位于另一侧。每个小岛是位于海洋中的一个点。对于任何一个雷达的安装 (均位于海岸线上)，只能覆盖 d 距离，因此海洋中的小岛被雷达安装所覆盖的条件是两者间的距离不超过 d 。
我们使用卡笛尔坐标系，将海岸线定义为 x 轴。海洋的一侧位于 x 轴上方，陆地的一侧位于下方。给定海洋中每个小岛的位置，并给定雷达安装的覆盖距离，您的任务是写一个程序，找出雷达安装的最少数量，使得所有的小岛都被覆盖。注意：小岛的位置以它的 x-y 坐标表示。
;
图 A: 雷达安装的示例输入
输入
输入由多个测试用例组成。每个测试用例的第一行，包含了两个整数 n (1<=n<=1000) 和 d，其中 n 是海洋中小岛的数目，d 是雷达安装的覆盖距离。接下来是 n 行，每行包含了两个整数，表示每个小岛的坐标。每组测试用例之间，以一个空行间隔。
输入终止于包含两个 0 的一行。
输出
对于每个测试用例，输出一行，包括测试用例的编号，以及雷达安装所需的最小数量。"-1" 个安装，表示该测试用例无解决方案。
示例输入
3 2
1 2
-3 1
2 1
1 2
0 2
0 0
示例输出
Case 1: 2
Case 2: 1
二、思路
一个岛屿的包含我们可以转化为区间问题，某个区间内安装一个雷达都能覆盖到这个岛屿。故我们只需要在这些区间里面选取最少的点（即安装最少的雷达）。一个岛屿我们就可以转化为一个区间，通过land[i].l = x - sqrt(d * d - y * y)求出左右端点即可
三、代码
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#define max(a, b) (a > b ? a : b)
using namespace std
;
const int N
= 1e3 + 5;
struct Island
{
double l
, r
;
friend bool operator < (Island a
, Island b
) {
return a
.r
< b
.r
;
}
} land
[N
];
int n
, ans
, x
, y
, maxy
, d
, cnt
= 1;
int main() {
while (scanf("%d%d", &n
, &d
), n
) {
ans
= 1;
maxy
= 0;
for (int i
= 0; i
< n
; i
++) {
scanf("%d%d", &x
, &y
);
maxy
= max(maxy
, y
);
land
[i
].l
= x
- sqrt(d
* d
- y
* y
);
land
[i
].r
= x
+ sqrt(d
* d
- y
* y
);
}
if (maxy
> d
) {
printf("Case %d: -1\n", cnt
++);
continue;
}
sort(land
, land
+ n
);
double r
= land
[0].r
;
for (int i
= 1; i
< n
; i
++) {
if (land
[i
].l
> r
) {
ans
++;
r
= land
[i
].r
;
}
}
printf("Case %d: %d\n", cnt
++, ans
);
}
return 0;
}
