<p>Given an array <code>rectangles</code> where <code>rectangles[i] = [x<sub>i</sub>, y<sub>i</sub>, a<sub>i</sub>, b<sub>i</sub>]</code> represents an axis-aligned rectangle. The bottom-left point of the rectangle is <code>(x<sub>i</sub>, y<sub>i</sub>)</code> and the top-right point of it is <code>(a<sub>i</sub>, b<sub>i</sub>)</code>.</p>

<p>Return <code>true</code> <em>if all the rectangles together form an exact cover of a rectangular region</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perectrec1-plane.jpg" style="width: 300px; height: 294px;" />
<pre>
<strong>Input:</strong> rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
<strong>Output:</strong> true
<strong>Explanation:</strong> All 5 rectangles together form an exact cover of a rectangular region.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perfectrec2-plane.jpg" style="width: 300px; height: 294px;" />
<pre>
<strong>Input:</strong> rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
<strong>Output:</strong> false
<strong>Explanation:</strong> Because there is a gap between the two rectangular regions.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perfecrrec4-plane.jpg" style="width: 300px; height: 294px;" />
<pre>
<strong>Input:</strong> rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
<strong>Output:</strong> false
<strong>Explanation:</strong> Because two of the rectangles overlap with each other.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= rectangles.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>rectangles[i].length == 4</code></li>
	<li><code>-10<sup>5</sup> &lt;= x<sub>i</sub> &lt; a<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>5</sup> &lt;= y<sub>i</sub> &lt; b<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
private:
    using point = std::pair<int, int>;

    void updateLargeArea(vector<int>& largeArea, vector<int>& rectangle){
        if(largeArea[0] > rectangle[0]){
            largeArea[0] = rectangle[0];
        }

        if(largeArea[1] > rectangle[1]){
            largeArea[1] = rectangle[1];
        }

        if(largeArea[2] < rectangle[2]){
            largeArea[2] = rectangle[2];
        }

        if(largeArea[3] < rectangle[3]){
            largeArea[3] = rectangle[3];
        }
        // cout << largeArea[0] << " " << largeArea[1] << " " << largeArea[2] << " " << largeArea[3] << " " << endl;
    }

    void pruneMap(map<point, int>& hash, vector<int>& largeArea){
        map<point, int>::iterator it;
        it = hash.find({largeArea[0], largeArea[3]});
        if(it != hash.end()) hash.erase(it);

        it = hash.find({largeArea[2], largeArea[3]});
        if(it != hash.end()) hash.erase(it);

        it = hash.find({largeArea[2], largeArea[1]});
        if(it != hash.end()) hash.erase(it);

        it = hash.find({largeArea[0], largeArea[1]});
        if(it != hash.end()) hash.erase(it);
    }

    void updateMap(map<pair<int,int>, int>& hash, vector<int>& rectangle){
        hash[{rectangle[0], rectangle[3]}]++;
        hash[{rectangle[2], rectangle[3]}]++;
        hash[{rectangle[2], rectangle[1]}]++;
        hash[{rectangle[0], rectangle[1]}]++;
    }

public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        map<point, int> hash;
        map<point, int>::iterator it;
        vector<pair<int, int>> corners;
        long long int totRectArea = 0;
        vector<int> largeArea(rectangles[0].begin(), rectangles[0].end());

        for(int i=0; i<rectangles.size(); i++){
            // corners = getCorners(rectangles[i]);

            totRectArea += static_cast<long long>(abs(rectangles[i][0] - rectangles[i][2])) * abs(rectangles[i][1] - rectangles[i][3]);

            updateLargeArea(largeArea, rectangles[i]);

            updateMap(hash, rectangles[i]);
        }

        if(totRectArea != static_cast<long long>(abs(largeArea[0] - largeArea[2])) * abs(largeArea[1] - largeArea[3])){
            // cout << totRectArea << " " << static_cast<long long>(abs(largeArea[0] - largeArea[2]) * abs(largeArea[1] - largeArea[3])) << endl;
            // cout << "first" << endl;
            return false;
        }

        it = hash.find({largeArea[0], largeArea[3]});
        if(it != hash.end() && it->second%2==0) return false;

        it = hash.find({largeArea[2], largeArea[3]});
        if(it != hash.end() && it->second%2==0) return false;

        it = hash.find({largeArea[2], largeArea[1]});
        if(it != hash.end() && it->second%2==0) return false;

        it = hash.find({largeArea[0], largeArea[1]});
        if(it != hash.end() && it->second%2==0) return false;

        pruneMap(hash, largeArea);
        
        for(it = hash.begin(); it!=hash.end(); it++){
            if(it->second%2 == 1){
                cout << "second" << endl;
                return false;
            }
        }

        return true;
    }
};
37000