206011 - 雷达问题

如图6.4所示,雷达装在一条直线上,直线上方是海洋,海洋中的岛屿位置已知,每一个雷达的扫描范围是一个半径为d的圆形区域,问最少需要多少个雷达覆盖所有岛屿。 图6.4

输入

输入包括多组测试数据(≤100),每组测试数据第一行为两个整数n(1≤n≤1 000)和d,即岛屿数和雷达扫描半径。随后n行,每行两个整数表示岛屿坐标。每组测试数据以空行间隔,所有测试数据以0 0结束。

输出

输出最少需要安装雷达数,每组一行。若无解以-1表示。

样例

输入

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

输出

Case 1: 2
Case 2: 1
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题