// Perfect Rectangle namespace std { template<> struct hash> { size_t operator()(const pair& x) const { return size_t(x.first) << 32 | x.second; } }; }; class Solution { public: bool isRectangleCover(vector>& rectangles) { int x0 = INT_MAX, x1 = INT_MIN, y0 = INT_MAX, y1 = INT_MIN; unordered_map, int> m; for (auto& a: rectangles) { x0 = min(x0, a[0]); y0 = min(y0, a[1]); x1 = max(x1, a[2]); y1 = max(y1, a[3]); int& m1 = m[make_pair(a[0], a[1])]; if (m1 & 1) return false; m1 |= 1; int& m2 = m[make_pair(a[0], a[3])]; if (m2 & 2) return false; m2 |= 2; int& m4 = m[make_pair(a[2], a[3])]; if (m4 & 4) return false; m4 |= 4; int& m8 = m[make_pair(a[2], a[1])]; if (m8 & 8) return false; m8 |= 8; } for (auto& i: m) { int x, y, mask = i.second; tie(x, y) = i.first; if ((x == x0 || x == x1) && (y == y0 || y == y1)) { if (__builtin_popcount(mask) != 1) return false; } else { if (mask != 3 && mask != 6 && mask != 12 && mask != 9 && mask != 15) return false; } } return true; } }; /// sweep line class Solution { public: bool isRectangleCover(vector>& rectangles) { long area = 0, x0 = INT_MAX, x1 = INT_MIN, y0 = INT_MAX, y1 = INT_MIN; vector>> b; set> active; for (auto& a: rectangles) { x0 = min(x0, long(a[0])); y0 = min(y0, long(a[1])); x1 = max(x1, long(a[2])); y1 = max(y1, long(a[3])); area += (long(a[2])-a[0])*(long(a[3])-a[1]); b.emplace_back(a[0]*2+1, make_pair(a[1], a[3])); b.emplace_back(a[2]*2, make_pair(a[1], a[3])); } sort(b.begin(), b.end()); for (auto& a: b) if (a.first % 2) { auto it = active.lower_bound(a.second); if (it != active.begin() && a.second.first < prev(it)->second || it != active.end() && it->first < a.second.second) return false; active.insert(it, a.second); } else active.erase(a.second); return area == (x1-x0)*(y1-y0); } };