Khái niệm
Đối với cặp điểm ‘n’ đã cho, nhiệm vụ của chúng ta là xác định bốn điểm sao cho chúng tạo thành một hình vuông có các cạnh song song với các trục x và y hoặc nếu không thì hiển thị “Không có hình vuông nào như vậy”. Cần lưu ý rằng nếu có thể có nhiều hơn một hình vuông thì hãy chọn hình vuông có diện tích tối đa.
Đầu vào
n = 6, points = (2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)
Đầu ra
Side of the square is: 3, points of the square are 2, 2 5, 2 2, 5 5, 5
Giải thích
Các điểm 2, 2 5, 2 2, 5 5, 5 tạo thành một hình vuông cạnh 3
Đầu vào
n= 6, points= (2, 2), (5, 6), (4, 5), (5, 4), (8, 5), (4, 2)
Đầu ra
No such square
Phương pháp
Phương pháp đơn giản - Chọn tất cả các cặp điểm có thể có với bốn vòng lặp lồng nhau và sau đó xác minh xem các điểm có tạo thành một hình vuông song song với các trục chính hay không. Người ta thấy rằng nếu có thì hãy xác minh xem nó có phải là hình vuông lớn nhất cho đến nay về diện tích hay không và lưu trữ kết quả, sau đó in kết quả vào cuối chương trình.
Độ phức tạp về thời gian - O (N ^ 4)
Phương pháp hiệu quả - Xây dựng một vòng lặp lồng nhau cho góc trên cùng bên phải và dưới cùng bên trái của hình vuông và tạo ra một hình vuông với hai điểm đó, sau đó xác minh xem hai điểm khác được giả định có thực sự tồn tại hay không. Bây giờ để xác minh xem một điểm có tồn tại hay không, hãy xây dựng bản đồ và lưu trữ các điểm trong bản đồ để giảm thời gian xác minh xem các điểm đó có tồn tại hay không.
Ví dụ
// 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;
} Đầu ra
Side of the square is: 3, points of the square are 2, 2 5, 2 2, 5 5, 5