Description

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


    我们使用笛卡尔坐标系，定义海岸线是x轴。海洋在 x 轴上方，陆地在下方。给定每个岛屿在海中的位置，以及雷达装置的覆盖距离，您的任务是编写一个程序来找到覆盖所有岛屿的最少雷达装置数量。请注意，岛的位置由其 xy 坐标表示。
                                                                              

Input Format

    输入由几个测试数据组成。
    对于每个测试数据：

        第一行包含两个整数 n  和 d，其中 n 是海中岛屿的数量，d 是雷达装置的覆盖距离。
        接下来是 n 行，每行包含两个整数，表示每个岛的位置坐标。然后是一个空行来分隔这些案例。


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

Output Format

    对于每个测试数据输出一行，由  测试数据编号  和  所需的最少雷达安装数 组成。“-1”安装意味着这种情况没有解决方案。

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

case1：2
case2：1

Hint

【数据规模】1<=n<=1000
【题目类型】线段覆盖问题

Source

贪心