雷达设备_python实现
本题若直接考虑雷达位置,每次遍历时都计算距离就有点麻烦了,不妨转化一下思路。由于雷达的覆盖范围是一个圈,因此我们可以将每个岛屿能被雷达覆盖的范围都提前计算出来,不难得到公式 left = x - (d^2 - y^2)^0.5
, right = x + (d^2 - y^2)^0.5
。
计算出来每个岛屿所能被覆盖的范围之后,不难发现,两个区间只要重合就可以只用一个雷达即可覆盖完全。因此我们就将问题转换为了计算重合区间数量的问题了。
如何计算重合区间的数量呢?首先需要对这些区间进行排序,那么是按照左端点进行排序,还是按照右端点进行排序呢?对于样例简单画图之后发现按照左端点排序很容易出错,考虑太复杂了。那么就按照右端点进行排序,这样判断标准就是当区间的左端点大于前一个区间右端点时,那么雷达不能覆盖这两个区间了,需要再加一个雷达。反之则继续遍历。
此外还需要注意,输入数据中可能会出现覆盖不到的点,因此需要在计算每个岛屿所能被覆盖的范围时进行判断。
n, d = map(int, input().split())
dots = []
for i in range(n):
dots.append(list(map(int, input().split())))
ans = 0
pos = []
state = True
for i in range(n):
if d ** 2 - dots[i][1] ** 2 >= 0:
l = dots[i][0] - (d ** 2 - dots[i][1] ** 2) ** 0.5
r = dots[i][0] + (d ** 2 - dots[i][1] ** 2) ** 0.5
pos.append([l, r])
else:
state = False
break
if state:
pos.sort(key = lambda x:(x[1]))
x = pos[0][1] #当前岛的右端点为雷达位置
for i in range(1, n):
if pos[i][0] > x:
ans += 1
x = pos[i][1]
if pos[i][0] <= x and i == n - 1:
ans += 1
print(ans)
else:
print(-1)