Hình chữ nhật hoàn hảo trong C++

Cho N hình chữ nhật trục tọa độ, kiểm tra xem chúng có cùng tạo thành một vùng hình chữ nhật chính xác hay không. Mỗi hình chữ nhật cho bằng điểm góc dưới trái và góc trên phải. Ô đơn vị: [1,1,2,2].

Ví dụ: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]] → true (5 hình chữ nhật tạo thành một hình chữ nhật lớn).

Phương pháp giải

Kiểm tra 2 điều kiện: (1) Tổng diện tích các hình nhỏ = diện tích hình bao ngoài. (2) 4 góc của hình bao ngoài chỉ xuất hiện 1 lần, các góc nội bộ xuất hiện 2 hoặc 4 lần (cặp nhau hủy nhau). Dùng set theo dõi các góc.

Ví dụ chương trình

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isRectangleCover(vector>& re) {
        unordered_set visited;
        int area = 0;
        int x2 = INT_MIN, x1 = INT_MAX;
        int y2 = INT_MIN, y1 = INT_MAX;
        
        for (auto& r : re) {
            x1 = min(r[0], x1);
            x2 = max(r[2], x2);
            y1 = min(r[1], y1);
            y2 = max(r[3], y2);
            area += (r[2] - r[0]) * (r[3] - r[1]);
            
            string s1 = to_string(r[0]) + to_string(r[1]);
            string s2 = to_string(r[0]) + to_string(r[3]);
            string s3 = to_string(r[2]) + to_string(r[3]);
            string s4 = to_string(r[2]) + to_string(r[1]);
            
            if (visited.count(s1)) visited.erase(s1); else visited.insert(s1);
            if (visited.count(s2)) visited.erase(s2); else visited.insert(s2);
            if (visited.count(s3)) visited.erase(s3); else visited.insert(s3);
            if (visited.count(s4)) visited.erase(s4); else visited.insert(s4);
        }
        
        string s1 = to_string(x1) + to_string(y1);
        string s2 = to_string(x2) + to_string(y1);
        string s3 = to_string(x1) + to_string(y2);
        string s4 = to_string(x2) + to_string(y2);
        
        if (!visited.count(s1) || !visited.count(s2) || !visited.count(s3) || !visited.count(s4) || visited.size() != 4)
            return false;
        return area == (x2 - x1) * (y2 - y1);
    }
};

int main() {
    Solution ob;
    vector> v = {{1,1,3,3}, {3,1,4,2}, {3,2,4,4}, {1,3,2,4}, {2,3,3,4}};
    cout << ob.isRectangleCover(v);
    return 0;
}

Đầu vào

{{1,1,3,3}, {3,1,4,2}, {3,2,4,4}, {1,3,2,4}, {2,3,3,4}}

Đầu ra

1