ধারণা
প্রদত্ত 'n' জোড়া বিন্দুর সাপেক্ষে, আমাদের কাজ হল চারটি বিন্দু নির্ধারণ করা যাতে তারা একটি বর্গক্ষেত্র তৈরি করে যার বাহুগুলি x এবং y অক্ষের সমান্তরাল বা "এমন কোন বর্গ নেই" প্রদর্শন করে। এটি উল্লেখ করা উচিত যে যদি একাধিক বর্গক্ষেত্র সম্ভব হয় তবে সর্বাধিক এলাকা সহ একটি নির্বাচন করুন৷
ইনপুট
n = 6, points = (2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)
আউটপুট
Side of the square is: 3, points of the square are 2, 2 5, 2 2, 5 5, 5
ব্যাখ্যা
বিন্দু 2, 2 5, 2 2, 5 5, 5 বাহুর একটি বর্গ গঠন করে 3
ইনপুট
n= 6, points= (2, 2), (5, 6), (4, 5), (5, 4), (8, 5), (4, 2)
আউটপুট
No such square
পদ্ধতি
সহজ পদ্ধতি − চারটি নেস্টেড লুপ সহ সমস্ত সম্ভাব্য জোড়া পয়েন্ট নির্বাচন করুন এবং তারপর যাচাই করুন যে বিন্দুগুলি একটি বর্গক্ষেত্র তৈরি করে যা প্রধান অক্ষের সমান্তরাল। এটা দেখা গেছে যে যদি হ্যাঁ হয় তবে এটি এখন পর্যন্ত ক্ষেত্রফলের দিক থেকে সবচেয়ে বড় বর্গ কিনা তা যাচাই করুন এবং ফলাফলটি সংরক্ষণ করুন এবং তারপর প্রোগ্রামের শেষে ফলাফলটি প্রিন্ট করুন।
সময়ের জটিলতা − O(N^4)
দক্ষ পদ্ধতি − বর্গক্ষেত্রের উপরের ডান এবং নীচের বাম কোণে একটি নেস্টেড লুপ তৈরি করুন এবং সেই দুটি বিন্দু দিয়ে একটি বর্গক্ষেত্র তৈরি করুন, তারপরে অনুমান করা হয়েছে যে অন্য দুটি বিন্দু আসলে বিদ্যমান কিনা তা যাচাই করুন। এখন একটি বিন্দু বিদ্যমান আছে কি না তা যাচাই করার জন্য, একটি মানচিত্র তৈরি করুন এবং পয়েন্টগুলি বিদ্যমান কিনা তা যাচাই করার জন্য সময় কমাতে মানচিত্রে পয়েন্টগুলি সংরক্ষণ করুন৷ তাছাড়া, এখন পর্যন্ত ক্ষেত্রফল অনুসারে বৃহত্তম বর্গক্ষেত্রটি পরীক্ষা করে রাখুন এবং শেষ পর্যন্ত এটি প্রদর্শন করুন৷
উদাহরণ
// C++ implemenataion of the above approach
#include <bits/stdc++.h>
using namespace std;
// Determine the largest square
void findLargestSquare1(long long int points1[][2], int n1){
// Used to map to store which points exist
map<pair<long long int, long long int>, int> m1;
// mark the available points
for (int i = 0; i < n1; i++) {
m1[make_pair(points1[i][0], points1[i][1])]++;
}
long long int side1 = -1, x1 = -1, y1 = -1;
// Shows a nested loop to choose the opposite corners of square
for (int i = 0; i < n1; i++) {
// Used to remove the chosen point
m1[make_pair(points1[i][0], points1[i][1])]--;
for (int j = 0; j < n1; j++) {
// Used to remove the chosen point
m1[make_pair(points1[j][0], points1[j][1])]--;
// Verify if the other two points exist
if (i != j && (points1[i][0]-points1[j][0]) == (points1[i][1]-points1[j][1])){
if (m1[make_pair(points1[i][0], points1[j][1])] > 0
&& m1[make_pair(points1[j][0], points1[i][1])] > 0) {
// So if the square is largest then store it
if (side1 < abs(points1[i][0] - points1[j][0])
|| (side1 == abs(points1[i][0] -points1[j][0])
&& ((points1[i][0] * points1[i][0]+ points1[i][1] * points1[i][1])
< (x1 * x1 + y1 * y1)))) {
x1 = points1[i][0];
y1 = points1[i][1];
side1 = abs(points1[i][0] - points1[j][0]);
}
}
}
// Used to add the removed point
m1[make_pair(points1[j][0], points1[j][1])]++;
}
// Used to add the removed point
m1[make_pair(points1[i][0], points1[i][1])]++;
}
// Used to display the largest square
if (side1 != -1)
cout << "Side of the square is : " << side1
<< ", \npoints of the square are " << x1 << ", " << y1<< " "<< (x1 + side1) << ", " << y1
<< " "
<< (x1) << ", " << (y1 + side1)
<< " "
<< (x1 + side1) << ", " << (y1 + side1) << endl;
else
cout << "No such square" << endl;
}
//Driver code
int main(){
int n1 = 6;
// given points
long long int points1[n1][2]= { { 2, 2 }, { 5, 5 }, { 4, 5 }, { 5, 4 }, { 2, 5 }, { 5, 2 }};
// Determine the largest square
findLargestSquare1(points1, n1);
return 0;
} আউটপুট
Side of the square is : 3, points of the square are 2, 2 5, 2 2, 5 5, 5
