দেওয়া কোঅর্ডিনেট সেট থেকে ন্যূনতম আয়তক্ষেত্রের ক্ষেত্রফল বের করা C++-তে

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