雷达问题
成绩 | 100 | 开启时间 | 2020年02月20日 星期四 19:50 |
折扣 | 0.8 | 折扣时间 | 2020年02月20日 星期四 19:50 |
允许迟交 | 是 | 关闭时间 | 2020年02月20日 星期四 19:50 |
输入文件 | radar.in | 输出文件 | radar.out |
【题目描述】雷达问题(radar) UVA Live 2519
如图6.4所示,雷达装在一条直线上,直线上方是海洋,海洋中的岛屿位置已知,每一个雷达的扫描范围是一个半径为d的圆形区域,问最少需要多少个雷达覆盖所有岛屿。
图6.4
【输入格式】
输入包括多组测试数据,每组测试数据第一行为两个整数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