用Python在不使用炸弹的情况下在矩形区域中找到一条连续路径的程序
假设我们有一个数组mat，其中元素的形式为[p,q,r]，其中p,q是几何坐标，r是半径值。数组中的项目是给定宽度w的矩形区域中炸弹的位置。矩形无限长，以x坐标x=0到x=w为界。炸弹位置中的r值表示炸弹的安全半径，这意味着任何小于炸弹半径的东西都会与它交战。所以，我们要做的是画一条连续的路径，从每颗炸弹下方开始，到每颗炸弹上方结束，而不与其中任何一个接触。如果我们能画这条线，我们将打印True，否则，我们打印False。
所以，如果输入像mat=
,w=4;那么输出将为False。
示例
让我们看看以下实现以获得更好的理解-
from bisect import bisect_left, insort
def solve(mat, w):
mat.sort(key=lambda i: i[0] - i[2])
temp = []
if mat[0][0] - mat[0][2] > 0:
return True
for p, q, r in mat:
min_wid, max_wid = p - r, p + r
if len(temp) == 0:
temp.append([p + r, p, q, r, p - r, p + r])
else:
mx = max(bisect_left(temp, [p - r, -p, q, r, 0, 0]) - 1, 0)
in_list = [p + r, p, q, r, p - r, p + r]
for i in range(mx, len(temp)):
if insec(temp[i], in_list):
max_wid = max(max_wid, temp[i][-1])
min_wid = min(min_wid, temp[i][-2])
in_list[-2] = min_wid
in_list[-1] = max_wid
insort(temp, in_list)
if min_wid <= 0 and max_wid >= w:
return False
return True
def insec(p, q):
x1, y1, x2, y2 = p[1], p[2], q[1], q[2]
r1, r2 = p[3], q[3]
d = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
dec = (r1 + r2) * (r1 + r2)
return d <= dec
print(solve([[0, 1, 2],[3, 2, 1], [2, 1, 1]], 4))输入
[[0, 1, 2],[3, 2, 1], [2, 1, 1]], 4输出结果
False