Tìm 4 điểm tạo thành vuông góc song song trục tọa độ trong Python

Cho n cặp điểm, tìm 4 điểm tạo thành hình vuông có cạnh song song trục x và y. Nếu nhiều vuông, chọn vuông diện tích lớn nhất. Không có thì trả về "not possible".

Ví dụ: n=6, points=[(2,2),(5,5),(4,5),(5,4),(2,5),(5,2)] → Cạnh 3, các điểm: (2,2), (5,2), (2,5), (5,5).

Thuật toán

1. Dùng dictionary my_map đếm tần suất mỗi điểm.
2. Duyệt cặp điểm (i, j) làm đối góc chéo tiềm năng: điều kiện x_i - x_j == y_i - y_j (để tạo vuông song song trục).
3. Kiểm tra hai đỉnh còn lại (x_i, y_j) và (x_j, y_i) có trong map không.
4. Cập nhật vuông lớn nhất (cạnh lớn nhất, tie-break bằng khoảng cách gốc).
5. Giảm tần suất khi kiểm tra, tăng lại sau (backtrack tần suất).

Ví dụ code

def get_square_points(points, n):
    my_map = {}
    for x, y in points:
        my_map[(x, y)] = my_map.get((x, y), 0) + 1
    side = -1
    x = y = -1
    for i in range(n):
        my_map[(points[i][0], points[i][1])] -= 1
        for j in range(n):
            my_map[(points[j][0], points[j][1])] -= 1
            if i != j and (points[i][0] - points[j][0]) == (points[i][1] - points[j][1]):
                if my_map.get((points[i][0], points[j][1]), 0) > 0 and \
                   my_map.get((points[j][0], points[i][1]), 0) > 0:
                    cur_side = abs(points[i][0] - points[j][0])
                    if side < cur_side or (side == cur_side and
                       (points[i][0]**2 + points[i][1]**2) < (x**2 + y**2)):
                        x, y = points[i][0], points[i][1]
                        side = cur_side
            my_map[(points[j][0], points[j][1])] += 1
        my_map[(points[i][0], points[i][1])] += 1
    if side != -1:
        print("Side:", side)
        print("Points:", (x, y), (x + side, y), (x, y + side), (x + side, y + side))
    else:
        print("No such square")

n = 6
points = [(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)]
get_square_points(points, n)

Input

6, [(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)]

Output

Side: 3
Points: (2, 2) (5, 2) (2, 5) (5, 5)