雷达设备 Radar Installation

题目描述

海岸线是一条无限长直线。建立平面直角坐标系，以海岸线为 x 轴，海面在 x 轴上方，陆地在下方。海面上的每个小岛看作一个点。

雷达只能安装在 x 轴上。一台雷达能够覆盖与它的距离不超过 d 的点。给出所有岛屿的坐标，求覆盖全部岛屿最少需要安装多少台雷达。如果不能覆盖全部岛屿，输出 -1。

下图为原题示意图，虚线圆表示雷达的覆盖范围。

输入格式

输入包含多组数据。每组第一行两个整数 n、d，随后 n 行，每行两个整数，表示一个岛屿的横纵坐标。 各组之间可能有空行。以一行 0 0 结束输入，这一行不作为测试组。

输出格式

对于第 k 组数据，输出 Case k: answer，其中 answer 是最少雷达数，无法覆盖时为 -1。

数据范围

1 ≤ n ≤ 1000，坐标和 d 为整数。原题未明确给出坐标及 d 的数值上限。

来源

UVA 1193 / POJ 1328。依据 UVA 官方PDF补齐本地题包遗漏的样例和示意图。原始题面PDF见附件。

原始题面 PDF

样例 1

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

Case 1: 2
Case 2: 1