ধরুন আমাদের 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
