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