Radar Installation

题意翻译

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

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=246&page=show_problem&problem=3634 [PDF](https://uva.onlinejudge.org/external/11/p1193.pdf)

输入输出格式

输入格式


输出格式


输入输出样例

暂无测试点