Tìm bốn điểm tạo thành vuông song song với trục tọa độ trong C++

Khái niệm

Cho 'n' cặp điểm, tìm bốn điểm tạo thành hình vuông có cạnh song song với trục x và y, hoặc in "Không có vuông nào". Nếu có nhiều vuông, chọn vuông diện tích lớn nhất.

Đầu vào

n = 6, points = (2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)

Đầu ra

Cạnh vuông: 3, các điểm: 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 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

Không có vuông nào

Phương pháp

Phương pháp đơn giản: chọn tất cả cặp điểm có thể với 4 vòng lặp lồng nhau, kiểm tra xem 4 điểm có tạo thành vuông song song trục tọa độ không. Nếu có, kiểm tra diện tích lớn nhất. Độ phức tạp O(N^4).

Phương pháp hiệu quả: dùng vòng lặp lồng cho góc trên bên phải và góc dưới bên trái của vuông, tạo vuông từ hai điểm đó, kiểm tra hai điểm còn lại có tồn tại không. Dùng map lưu các điểm để kiểm tra tồn tại O(1). Theo dõi vuông diện tích lớn nhất.

Ví dụ

// C++ tìm vuông lớn nhất
#include <bits/stdc++.h>
using namespace std;

void findLargestSquare1(long long int points1[][2], int n1){
    map<pair<long long int, long long int>, int> m1;
    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;
    for (int i = 0; i < n1; i++) {
        m1[make_pair(points1[i][0], points1[i][1])]--;
        for (int j = 0; j < n1; j++) {
            m1[make_pair(points1[j][0], points1[j][1])]--;
            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) {
                    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]);
                    }
                }
            }
            m1[make_pair(points1[j][0], points1[j][1])]++;
        }
        m1[make_pair(points1[i][0], points1[i][1])]++;
    }
    if (side1 != -1)
        cout << "Cạnh vuông: " << side1 << ", \nCác điểm: " << x1 << ", " << y1 << " " << (x1 + side1) << ", " << y1 << " " << (x1) << ", " << (y1 + side1) << " " << (x1 + side1) << ", " << (y1 + side1) << endl;
    else
        cout << "Không có vuông nào" << endl;
}

int main(){
    int n1 = 6;
    long long int points1[n1][2]= { { 2, 2 }, { 5, 5 }, { 4, 5 }, { 5, 4 }, { 2, 5 }, { 5, 2 }};
    findLargestSquare1(points1, n1);
    return 0;
}

Đầu ra

Cạnh vuông: 3, Các điểm: 2, 2 5, 2 2, 5 5, 5