मान लीजिए हमारे पास 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
