贪心

首先, 对于每个海岛, 求出海岸上能够侦查到这个海岛的区间. 如果y > d, 区间为空区间, 直接输出”-1”, 退出程序.
根据区间的右端点进行排序, 依次考虑这些海岛.
第一个雷达设置在第一个右端点上.
然后找出第一个左端点 > 这个雷达位置, 然后在这个区间的右端点设置第二个雷达.
其他的雷达以此类推.
之所以将雷达设置在右端点上, 目的是既可以不遗漏这个海岛, 又尽量靠右, 去覆盖更多的海岛, 左端点 <= 这个雷达位置的海岛, 都已经被覆盖了, 当左端点 > 这个雷达位置的时候, 这个海岛没有被覆盖, 必须在这个海岛设置一个雷达, 同样道理, 设置在这个海岛区间的右端点是最优的.

时间复杂度

排序O(N*log(N))

Python 代码

def solve():
    n, d = map(int, input().split())
    islands = []
    for i in range(n):
        x, y = map(int, input().split())
        if y > d: 
            print(-1)
            return
        delta = (d ** 2 - y ** 2) ** 0.5
        left, right = x - delta, x + delta
        islands.append((right, left))
    islands.sort()

    pos = islands[0][0]
    ans = 1
    for i in range(1, n):
        right, left = islands[i]
        if left > pos:
            pos = right
            ans += 1
    print(ans)


solve()