在Python中查找矩形区域内不接触炸弹的连续路径的程序

假设我们有一个数组mat，其中元素的形式为[p，q，r]，其中p，q是几何坐标，r是半径值。数组中的项目是给定宽度w矩形区域内炸弹的位置。矩形无限长，受到x坐标x = 0至x = w的界限。炸弹位置中的r值表示炸弹的安全半径，这意味着小于炸弹的半径的任何东西都会引爆它。因此，我们必须绘制一条连续的路径，从每个炸弹下方开始，结束于每个炸弹上方，而不接触任何一个炸弹。如果我们能绘制出这条线路，我们将打印True，否则我们将打印False。

因此，如果输入如下所示mat =

0	1	2
3	2	1
2	1	1

，w = 4; 则输出将为False。

为了解决这个问题，我们将按照以下步骤进行 –

定义函数insec() 。这将采用p，q
- x1:= p [1]，x2:= p [2]
- y2:= q [1]，y4:= q [2]
- r1:= p [3]，r2:= q [3]
- d：=（x1-x2）（x1-x2）+（y1-y2）（y1-y2）
- dec：=（r1 + r2）*（r1 + r2）
- 如果d <= dec，则返回True，否则返回False
基于x坐标值对矩阵进行排序
temp：一个新列表
如果mat [0] [0] – mat [0] [2]> 0，则
- 返回True
对于mat中的每个p，q，r，执行以下操作
- min_wid：= p – r
- max_wid：= p + r
- 如果temp的大小与0相同，则
  - 在temp的末尾添加包含（p + r，p，q，r，p – r，p + r）的列表
- 否则，
  - mx：=（维护排序顺序的列表[p – r，-p，q，r，0，0]中元素可以插入的位置 – 1）的最大值，0
  - in_list：一个包含元素（p + r，p，q，r，p – r，p + r）的新列表
  - 对于范围mx到temp大小的i，执行以下操作
  - 如果insec（temp [i]，in_list）为True，则
    - max_wid：=（max_wid，temp [i，-1]）的最大值
  - min_wid：=（min_wid，temp [i，-2]）的最小值
  - in_list的倒数第二个元素：= min_wid
  - in_list的最后一个元素：= max_wid
  - 在temp中插入in_list，维护排序顺序
- 如果min_wid <= 0且max_wid >= w，则
  - 返回False
返回True

示例

让我们看以下实现，以获得更好的理解 –

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))