สมมติว่ามีอาร์เรย์ของจุดบนระนาบ XY เราต้องหาพื้นที่น้อยที่สุดของสี่เหลี่ยมผืนผ้าที่สามารถสร้างได้จากจุดเหล่านี้ ด้านของสี่เหลี่ยมผืนผ้าควรขนานกับแกน X และ Y หากเราไม่สามารถสร้างสี่เหลี่ยมผืนผ้าได้ ให้คืนค่า 0 ดังนั้นถ้าอาร์เรย์จุดเป็น [(1, 1), (1, 3), (3, 1), (3, 3), (2, 2)] ผลลัพธ์จะเป็น 4 สี่เหลี่ยมผืนผ้าสามารถสร้างได้โดยใช้จุด (1, 1), (1, 3), (3, 1) และ (3, 3)
เพื่อแก้ปัญหานี้ ให้จัดกลุ่มจุดตามพิกัด x ดังนั้นจุดบนเส้นตรงแนวตั้งจะอยู่กลุ่มเดียวกัน จากนั้นสำหรับแต่ละคู่ของจุดในกลุ่ม เช่น (x, y1) และ (x, y2) เราจะหาสี่เหลี่ยมผืนผ้าที่เล็กที่สุดด้วยคู่นี้เป็นขอบขวาสุดของสี่เหลี่ยมที่จะสร้าง เราสามารถทำได้โดยติดตามคู่อื่นๆ ที่เราเคยเยี่ยมชมมาก่อน ต่อไปคืนค่าพื้นที่น้อยที่สุดของสี่เหลี่ยมผืนผ้าที่ได้
ตัวอย่าง
import collections
def findMinArea(Arr):
columns = collections.defaultdict(list)
for x, y in Arr:
columns[x].append(y)
lastx = {}
ans = float('inf')
for x in sorted(columns):
col = columns[x]
col.sort()
for j, y2 in enumerate(col):
for i in range(j):
y1 = col[i]
if (y1, y2) in lastx:
ans = min(ans, (x - lastx[y1, y2]) * (y2 - y1))
lastx[y1, y2] = x
if ans < float('inf'):
return ans
else:
return 0
A = [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]]
print('Minimum area of rectangle:', findMinArea(A))
ผลลัพธ์
Minimum area of rectangle: 4
