J4 实践-3 装配雷达

题目描述

假设海岸线是无限直线。土地位于海岸的一侧，海洋位于另一侧。每个小岛都位于海边。并且任何位于海岸线的雷达装置只能覆盖 $d$ 距离，因此如果它们之间的距离最多为 $d$ ，则可以通过半径装置覆盖海中的岛屿。

我们使用笛卡尔坐标系，定义海岸线是 $X$ 轴。海侧在 $X$ 轴上方，陆侧在下方。考虑到每个岛屿在海中的位置，并考虑到雷达装置覆盖范围的距离，您的任务是编写一个程序，以找到覆盖所有岛屿的最小数量的雷达装置。注意，岛的位置由其 $XY$ 坐标表示。

下图阿雷达装置的示例输入

输入格式

输入包含几个测试用例。每种情况的第一行包含两个整数 $n$ 和 $d$，其中 $n$ 是海中岛屿的数量，$d$ 是雷达装置的覆盖距离。接下来是 $n$ 行，每行包含两个整数，表示每个岛的位置坐标。然后是一个空白行来分隔案例。

输入由包含零对的行终止。

输出格式

对于每个测试用例输出，一行包含测试用例编号，然后是所需的最少数量的雷达安装。“ - 1”安装意味着没有解决方案。

样例输入

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

样例输出

Case 1: 2
Case 2: 1

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1 \le n \le 1000$ 。