#2217. 海岸雷达Radar Installation
海岸雷达Radar Installation
题面翻译
描述:
假设海岸线是一条无限长的直线,陆地位于海岸线的一边,大海位于海岸线的另一边。大海中有许多小岛。某安全部门为了监视这些岛上是否有敌人入侵,打算在海岸线上安装若干个雷达来检测岛屿的情况。每个雷达的覆盖范围是以雷达中心为圆心,半径为 的圆形区域。
我们用平面之间坐标系来表示整个区域,海岸线为 轴,大海位于 轴上方,陆地位于 轴下方。为了节约成本,安全部门想使用最少的雷达覆盖所有的岛屿。现在已知每个岛屿的坐标 和雷达的覆盖半径 ,你的任务就是计算出能够覆盖所有岛屿的最少雷达数量。
输入格式
输入包含若干组数据。
每组数据的第一行有两个整数 和 ,分别表示岛屿的数量和雷达的覆盖半径,之后的 行,每行有两个整数,表示第 个岛屿的坐标 。
相邻的两组数据使用一个空行隔开。
输出格式
对于每一组数据的输出格式为 ,表示第 组数据中最少需要 个雷达来覆盖所有的岛屿; 表示这组数据无解(无法覆盖所有的岛屿)
样例 #1
样例输入 #1
3 2
1 2
-3 1
2 1
1 2
0 2
3 3
0 1
0 3
10 2
样例输出 #1
Case 1: 2
Case 2: 1
Case 3: 2
Statistics
Related
In following contests: