Pythonで爆弾を使用せずに、長方形の領域で連続したパスを見つけるプログラム

要素がこの形式[p、q、r]である配列マットが与えられたとします。ここで、p、qは幾何座標であり、rは半径値です。配列内のアイテムは、指定された幅wの長方形の領域内の爆弾の位置です。長方形は無限に長く、x座標x=0からx=wで囲まれています。爆弾の位置のr値は、爆弾の安全半径を示します。これは、爆弾の半径よりも小さいものが爆弾に当たることを意味します。したがって、私たちがしなければならないことは、すべての爆弾の下から始まり、すべての爆弾の上で終わり、爆弾のいずれにも関与しない連続した経路を描くことです。この線を描画できる場合はTrueを出力し、そうでない場合はFalseを出力します。

したがって、入力がmat =

、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を返す
• マット内の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の最後から2番目の要素：=min_wid
    • in_listのlast_element：=max_wid
    • ソートされた順序を維持しながら、一時的に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))

入力

[[0, 1, 2],[3, 2, 1], [2, 1, 1]], 4

出力

False