安装雷达
时间限制:1秒 内存限制:256M
【题目描述】
在一个坐标系中,\(x\) 轴代表海岸线,\(x\) 轴以上是大海。在海上有 \(n\) 个岛屿。现在打算在 \(x\) 轴上建一些雷达,一部雷达的覆盖范围为半径为 \(d\) 的圆。
请你计算在 \(x\) 轴上最少建多少部雷达,才能把全部的岛屿覆盖起来,如果不能覆盖,输出 -1。
【输入格式】
输入包含若干组数据,每组数据的第一行为整数 \(n\) 和 \(d\) ,它们的意义如题目描述。
接下来的 \(n\) 行,每行为两个整数 \(x,y\),表示一个岛屿的坐标。输入以 0 0 结束。
【输出格式】
每组数据输出一行,如果建立的雷达能覆盖所有岛屿,输出最少需要安装的雷达数目,否则输出-1。
【输入输出样例】
Input
3 2
1 2
-3 1
2 1
1 2
0 2
0 0
Output
Case 1: 2
Case 2: 1
【数据限制】
对于 \(100\%\) 的数据,\(1≤n≤1000\),\(1≤x,y,d≤10^9\)。
【来源】
Mr.he