আয়তের ক্ষেত্রফল এর দো flanc-র গুণফল হিসেবে হিসাব করা হয়। সব আয়তের চারটি flanc থাকে যাতে বিপরীত দুটি flanc সমান। ক্ষেত্রফল বের করতে দৈর্ঘ্য ও প্রস্থ — দুটি flanc লাগে।
আমাদের একটি অ্যারে দেওয়া আছে যেটিতে আয়তের চার flanc-এর মান র্যান্ডম অর্ডারে আছে। টাস্ক হলো অ্যারে থেকে সর্বোচ্চ দুটি জোড়া flank বের করে আয়তের সর্বোচ্চ সম্ভাব্য ক্ষেত্রফল বের করা।
ইনপুট
Arr[] = { 1, 2, 1, 3, 4, 4, 2, 3, 5, 7 }
আউটপুট − Maximum area rectangle by picking four sides from array: 12
ব্যাখ্যা − অ্যারেটি ডিসেন্ডিং অর্ডারে সর্ট করলে পাই,
Arr[] = { 7, 5, 4, 4, 3, 3, 2, 2, 1, 1 }
সর্বোচ্চ দুটি জোড়া flank (মোট চার flank) হলো { (4,4), (3,3) }। তাই সর্বোচ্চ ক্ষেত্রফল = ১২ বর্গ ইউনিট।
ইনপুট
Arr[] = { 8, 2, 5, 3, 4, 9, 8, 3, 5, 7 }
আউটপুট − Maximum area rectangle by picking four sides from array: 40
ব্যাখ্যা − ডিসেন্ডিং অর্ডারে সর্ট করলে,
Arr[] = { 9, 8, 8, 7, 5, 5, 4, 3, 3, 2 }
সর্বোচ্চ দুটি জোড়া flank হলো { (8,8), (5,5) }। সর্বোচ্চ ক্ষেত্রফল = ৪০ বর্গ ইউনিট।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- একটি ইন্টিজার অ্যারে ঘোষণা করুন যেটিতে আয়তের flank জোড়া থাকে।
- অ্যারের সাইজ সংরক্ষণ করার ভ্যারিয়েবল তৈরি করুন।
maxArea(int arr[], int n)ফাংশনটি আয়তের সর্বোচ্চ ক্ষেত্রফল বের করতে ব্যবহৃত হয়।- ফাংশনের ভিতরে
Dim[2]অ্যারে তৈরি করুন সর্টেড অ্যারে থেকে সর্বোচ্চ দুটি flank সংরক্ষণ করতে। - অ্যারেটি ডিসেন্ডিং অর্ডারে সর্ট করা থাকায় সর্বোচ্চ ৪টি flank শুরুতে থাকবে। অ্যারেটি ট্রাভার্স করে flank জোড়া খুঁজুন।
Dim[]কে ০ দিয়ে ইনিশিয়ালাইজ করুন।- হোইল লুপে শর্ত রাখুন যে
j < 2(Dim-এ দুটি flank পাওয়া যাক) এবংi < n। - যদি flank জোড়া পাওয়া যায় (
arr[i] == arr[i+1]), তবে সেটিDim[j]-এ সংরক্ষণ করুন এবংjবাড়ান। - ফলাফল হিসেবে
Dim[0] * Dim[1]রিটার্ন করুন।
উদাহরণ
#include <iostream>
#include <algorithm>
using namespace std;
int maxArea(int arr[], int n) {
int dim[2] = {0};
int i = 0, j = 0;
sort(arr, arr + n, greater<int>()); // ডিসেন্ডিং অর্ডারে সর্ট
while (j < 2 && i < n) {
if (arr[i] == arr[i + 1]) {
dim[j++] = arr[i];
i++; // জোড়া পাওয়া গেলে এক্সট্রা ইনক্রিমেন্ট
}
i++;
}
return dim[0] * dim[1];
}
int main() {
int arr[] = { 1, 8, 5, 1, 8, 2, 5, 3 };
int n = 8;
cout << "Maximum area of rectangle by picking four sides from array: " << maxArea(arr, n);
return 0;
}আউটপুট
Maximum area of rectangle by picking four sides from array: 40
