391. Perfect Rectangle

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]
Return true. All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

rectangles = [
  [1,1,2,3],
  [1,3,2,4],
  [3,1,4,2],
  [3,2,4,4]
]
Return false. Because there is a gap between the two rectangular regions.

Example 3:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [3,2,4,4]
]

Return false. Because there is a gap in the top center.

Example 4:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,2,4,4]
]
Return false. Because two of the rectangles overlap with each other.

S1： 观察总结corner pattern, 比较难想到 O(n)

满足题意的input需要满足两个条件：

1. 所有小rectangle的面积之和等于最终的大rectangle的面积
2. 除了大rectangle的四个顶点point在所有小rectangle中只出现了一次以外，其余小rectangle的顶点point都出现了偶数次

unorderded_set没有pair和vector对应的hash function所以把坐标转化为string

    bool isRectangleCover(vector<vector<int>>& rectangles) {
        unordered_set<string> points;
        int x1 = INT_MAX, x2 = INT_MIN, y1 = INT_MAX, y2 = INT_MIN;
        int area = 0;
        vector<string> p(4);
        for (vector<int>& rect : rectangles) {          
            p[0] = to_string(rect[0]) + ' ' + to_string(rect[1]);
            p[1] = to_string(rect[2]) + ' ' + to_string(rect[1]);
            p[2] = to_string(rect[2]) + ' ' + to_string(rect[3]);
            p[3] = to_string(rect[0]) + ' ' + to_string(rect[3]);
            area += abs(rect[2] - rect[0]) * abs(rect[3] - rect[1]);
            x1 = min(rect[0], x1);
            x2 = max(rect[2], x2);
            y1 = min(rect[1], y1);
            y2 = max(rect[3], y2);
            for (int i = 0; i < 4; ++i) {
                if (points.find(p[i]) == points.end()) {
                    points.insert(p[i]);
                } else {
                    points.erase(p[i]);
                }
            }
        }
        if (points.size() != 4) return false;
        p[0] = to_string(x1) + ' ' + to_string(y1);
        p[1] = to_string(x2) + ' ' + to_string(y1);
        p[2] = to_string(x2) + ' ' + to_string(y2);
        p[3] = to_string(x1) + ' ' + to_string(y2);
        for (int i = 1; i < 4; ++i) {
            if (points.find(p[i]) == points.end()) return false;      
        }
        return (x2 - x1) * (y2 - y1) == area;
    }