สมมติว่าเรามีอาร์เรย์ของบางจุดในระนาบ 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
