Greedy

POJ-1328 Radar Installation

题目传送门: POJ 1328

给一个平行与 x 轴的海岸线,y < 0 部份为土地,y > 0部份为海,在海上有小岛,小岛的坐标给出,现在在海岸线上装雷达,雷达的覆盖范围为半径为 d 的圆,求最少要多少雷达能够覆盖所有岛,若是无法覆盖所有的岛,输出 -1 。

具体来说,先以 x 坐标排序,对于一个岛,求出可以覆盖它的雷达的位置在 x 轴上的范围,若两可检测的两小岛的雷达范围有重叠,则两小岛可公用一个雷达检测,最后用贪心来求雷达的最小数量就行。

若小岛的 y 坐标大于雷达的半径,就无法检测到了。