หา 4 จุดที่สร้างสี่เหลี่ยมจัตุรัสขนานแกน x,y ใน Python

โจทย์: กำหนด n จุด หา 4 จุดที่สร้างสี่เหลี่ยมจัตุรัสขนานแกน พื้นที่มากที่สุด ถ้าไม่มี → "not possible"

ตัวอย่าง: points=[(2,2),(5,5),(4,5),(5,4),(2,5),(5,2)] → สี่เหลี่ยม (2,2),(5,2),(2,5),(5,5) side=3

อัลกอริทึม O(n²) ใช้ Hash Map

1. เก็บจุดทั้งหมดใน hash map (ดิกชันนารี) เพื่อ O(1) lookup
2. วนคู่จุด (i, j) ทุกคู่: ถ้า |x_i - x_j| == |y_i - y_j| → เป็น diagonal ของสี่เหลี่ยมจัตุรัสขนานแกน
3. ตรวจสอบจุดอีก 2 มุม: (x_i, y_j) และ (x_j, y_i) อยู่ใน map หรือไม่
4. คำนวณ side = |x_i - x_j| เก็บค่าสูงสุด (ถ้าเท่ากัน เลือกจุดที่อยู่ใกล้ origin กว่า)

ตัวอย่างโค้ด

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]):
                p1 = (points[i][0], points[j][1])
                p2 = (points[j][0], points[i][1])
                if my_map.get(p1, 0) > 0 and my_map.get(p2, 0) > 0:
                    curr_side = abs(points[i][0] - points[j][0])
                    if (side < curr_side or 
                        (side == curr_side and (points[i][0]**2 + points[i][1]**2) < (x**2 + y**2))):
                        x, y = points[i][0], points[i][1]
                        side = curr_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")

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

ผลลัพธ์

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

สรุป: ใช้ diagonal property: สี่เหลี่ยมจัตุรัสขนานแกนมี diagonal ที่ dx == dy ใช้ hash map ตรวจสอบมุมอื่น 2 จุด O(n²) time O(n) space