/ Vijos / 题库 /

安装雷达

安装雷达

时间限制: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

信息

ID
1796
难度
(无)
分类
贪心 | 其他 | 排序 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
2
上传者