Cho mảng mat chứa các phần tử dạng [p, q, r] với p, q là tọa độ hình học và r là bán kính an toàn của bom. Vùng chữ nhật có chiều rộng w, giới hạn bởi x = 0 đến x = w và kéo dài vô hạn theo trục y. Cần vẽ một đường liên tục bắt đầu từ dưới tất cả bom và kết thúc ở trên tất cả bom mà không chạm vào vùng an toàn của bất kỳ bom nào. Trả về True nếu có thể, ngược lại False.
Ví dụ: mat = [[0,1,2],[3,2,1],[2,1,1]], w = 4 → kết quả False.
Giải thuật
- Định nghĩa hàm
insec(p, q)kiểm tra hai bom có giao nhau không dựa trên khoảng cách tâm và tổng bán kính - Sắp xếp ma trận theo tọa độ x
- Duyệt qua từng bom, theo dõi khoảng cách an toàn tối thiểu/tối đa
- Nếu khoảng cách an toàn bao phủ toàn bộ chiều rộng
w(từ ≤ 0 đến ≥ w) thì trả vềFalse - Ngược lại trả về
True
Ví dụ triển khai
from bisect import bisect_left, insort
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)**2 + (y1 - y2)**2
dec = (r1 + r2)**2
return d <= dec
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
print(solve([[0, 1, 2], [3, 2, 1], [2, 1, 1]], 4))Đầu vào
[[0, 1, 2], [3, 2, 1], [2, 1, 1]], 4
Đầu ra
False