컨셉
주어진 'n' 쌍의 점과 관련하여 우리의 임무는 4개의 점을 결정하여 측면이 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
방법
간단한 방법 − 4개의 중첩 루프가 있는 가능한 모든 포인트 쌍을 선택한 다음 포인트가 주축에 평행한 정사각형을 형성하는지 확인합니다. 그렇다면 지금까지 면적으로 가장 큰 정사각형인지 확인하고 그 결과를 저장하고 프로그램 마지막에 결과를 출력하는 것을 보았다.
시간 복잡도 - 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