কনসেপ্ট
n জোড়া পয়েন্ট দেওয়া আছে। X ও Y অক্ষের সমান্তরাল বর্গ তৈরি করে এমন চার পয়েন্ট খুঁজে বের করুন। একাধিক বর্গ হলে সর্বোচ্চ ক্ষেত্রফল वालাটি বেছে নিন। না পেলে "No such square" প্রিন্ট করুন।
ইনপুট ১
n=6, points=(2,2),(5,5),(4,5),(5,4),(2,5),(5,2)
আউটপুট ১
Side of the square is: 3, points: 2,2 5,2 2,5 5,5
ইনপুট ২
n=6, points=(2,2),(5,6),(4,5),(5,4),(8,5),(4,2)
আউটপুট ২
No such square
পদ্ধতি
দক্ষ পদ্ধতি (O(n²)): ম্যাপ (map) দিয়ে পয়েন্টগুলো স্টোর করুন। دوটি নেস্টেড লুপ দিয়ে বর্গের বিপরীত কোণ (টপ-রাইট ও বটম-লেফট) বেছে নিন। বাকি দুটি কোণ ম্যাপে আছে কিনা চেক করুন। সর্বোচ্চ ক্ষেত্রফলের বর্গ আপডেট করুন।
উদাহরণ (C++ কোড)
// C++: সর্বোচ্চ বর্গ খুঁজে বের
#include <bits/stdc++.h>
using namespace std;
void findLargestSquare1(long long int points1[][2], int n1) {
map, int> m1;
for (int i=0; i 0 && m1[{points1[j][0], points1[i][1]}] > 0) {
long long int curSide = abs(points1[i][0]-points1[j][0]);
if (side1 < curSide || (side1==curSide && (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=curSide;
}
}
}
m1[{points1[j][0], points1[j][1]}]++;
}
m1[{points1[i][0], points1[i][1]}]++;
}
if (side1 != -1)
cout << "Side: " << side1 << ", Points: " << x1 << "," << y1 << " " << x1+side1 << "," << y1 << " " << x1 << "," << y1+side1 << " " << x1+side1 << "," << y1+side1 << endl;
else cout << "No such square" << endl;
}
int main() {
int n1=6;
long long int points1[6][2] = {{2,2},{5,5},{4,5},{5,4},{2,5},{5,2}};
findLargestSquare1(points1, n1);
return 0;
}
আউটপুট
Side of the square is : 3, points of the square are 2, 2 5, 2 2, 5 5, 5
