Chương trình tìm điểm hợp lệ gần nhất cùng tọa độ x hoặc y bằng Python

Cho tập điểm pts và điểm hiện tại (x, y). Điểm hợp lệ: cùng x hoặc cùng y với điểm hiện tại. Tìm chỉ số điểm hợp lệ có khoảng cách Manhattan nhỏ nhất. Nếu bằng nhau, lấy chỉ số nhỏ nhất.

Ví dụ: pts = [(1,2),(3,1),(3,4),(2,3),(4,4)], pt = (2,4). Điểm hợp lệ: (3,4) khoảng cách 1, (2,3) khoảng cách 1. Chỉ số (3,4) là 2 < 3 → trả về 2.

Thuật toán giải quyết

• x, y := pt.
• idx := -1, smallest := vô cực.
• Duyệt p trong pts:
  • Nếu p[0]==x hoặc p[1]==y: dist = |x-p[0]| + |y-p[1]|.
  • Nếu dist < smallest: cập nhật idx, smallest.
  • Nếu dist == smallest và chỉ số p < idx: cập nhật idx.
• Trả về idx.

Ví dụ triển khai

def solve(pts, pt):
    x, y = pt
    idx = -1
    smallest = float("inf")
    for p in pts:
        if p[0] == x or p[1] == y:
            dist = abs(x - p[0]) + abs(y - p[1])
            if dist < smallest:
                idx = pts.index(p)
                smallest = dist
            elif dist == smallest:
                if pts.index(p) < idx:
                    idx = pts.index(p)
                    smallest = dist
    return idx

pts = [(1,2),(3,1),(3,4),(2,3),(4,4)]
pt = (2,4)
print(solve(pts, pt))

Đầu vào

[(1,2),(3,1),(3,4),(2,3),(4,4)], (2,4)

Đầu ra

2