Python에서 폭탄을 사용하지 않고 직사각형 영역에서 연속 경로를 찾는 프로그램

<시간/>

요소가 [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이면
- 참 반환
매트의 각 p, q, r에 대해 do
- min_wid :=p - r
- max_wid :=p + r
- temp의 크기가 0과 같으면
  - temp의 끝에 (p + r, p, q, r, p - r, p + r)을 포함하는 목록 추가
- 그렇지 않으면
  - mx :=maximum of (정렬된 순서를 유지하면서 목록 [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의 last_element :=max_wid
  - 정렬 순서를 유지하면서 임시로 in_list 삽입
- min_wid <=0이고 max_wid>=w이면
  - 거짓을 반환
참 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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