AcWing 112. 雷达设备 python3 贪心带思路+注释
原题链接
中等
作者:
嶋野的狂犬
,
2024-10-25 20:59:16
,
所有人可见
,
阅读 1
# 本题可做以下转化
# 由于圆形很难处理,所有的雷达又只在x轴上
# 我们可以将每个小岛可以选择的雷达范围投影到x轴上,
# 然后寻找这些投影之间有无重叠,如果有重叠,则可以通过选择位置同时覆盖多个岛
# 贪心策略:将所有范围区间按照右端点升序排序,
# 第一个点(雷达位置)选择第一个区间的右端点,
# 随后判断上一个选择的点是否在下一个区间,如果在则跳过该区间,如果不在则选择此区间的右端点
# 因为选择最右端点,所以被下一个区间包含的可能性最大
flag=0
n,d=map(int,input().split())
a=[]
l=[]
for _ in range(n):
a.append(list(map(int,input().split())))
# 将所有投影区间存到l中
for x,y in a:
if d*d-y*y<0:
flag=1
else:
lx=pow(d*d-y*y,0.5)
l.append([x-lx,x+lx])
# 按第二个元素(区间右端点)升序排序
l.sort(key=lambda x:x[1])
# 初始化选择点为第一个区间的右端点
x=l[0][1]
res=1
for ll,lr in l[1:]:
if ll<=x<=lr:
continue
else:
x=lr
res+=1
if flag:
print(-1)
else:
print(res)