391. Perfect Rectangle

问题：

给定多个小矩形，rec[i]={x1,y1,x2,y2}

• (x1, y1) 代表小矩形的↙?左下顶点坐标
• (x2, y2) 代表小矩形的↗?右上顶点坐标

这些小矩形是否能组成一个完美矩形。

要求：不能存在重叠or空余的内部空间。

Example 1:
Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
Output: true
Explanation: All 5 rectangles together form an exact cover of a rectangular region.

Example 2:
Input: rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
Output: false
Explanation: Because there is a gap between the two rectangular regions.

Example 3:
Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]
Output: false
Explanation: Because there is a gap in the top center.

Example 4:
Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
Output: false
Explanation: Because two of the rectangles overlap with each other.
 
Constraints:
1 <= rectangles.length <= 2 * 10^4
rectangles[i].length == 4
-10^5 <= xi, yi, ai, bi <= 10^5

example 1:                                                                                              example 2:

example 3:                                                                                              example 4:

解法：

参考labuladong

思路：

我们需要从两方面考虑：

• 顶点：由于以下?? ，可得：最终得到Count(奇数次顶点)==4 && 该4顶点=={所有顶点的min_x, min_y, max_x, max_y 两两组合} 
  • 所有矩形的所有顶点，若重复偶数次，则最终形成的矩形中，不构成顶点。
  • 重复奇数次，则构成顶点。
• 面积 ：由于以下?? ，可得：要求面积和==最终剩下的4个顶点构成的面积(max_x-min_x)*(max_y-max_y) 
  • 所有矩形的面积和=最终构成矩形的面积

代码参考：

 1 typedef pair<int,int> pii;
 2 class Solution {
 3 public:
 4     string toString(pii pt) {
 5         return to_string(pt.first) + "_" + to_string(pt.second);
 6     }
 7     bool isRectangleCover(vectorint>>& rectangles) {
 8         unordered_set<string> ps;//point set
 9         //if a same point appear even times, then it may not be one of the final 4 points.
10         //we should delete it from point set.
11         //1. the final 4 points == min x, min y, max x, max y -> 4 points
12         //2. Area(1's 4 point) == SUM of Area(each part rectangles).
13         //we can definite this is a perfect rectangle.
14         int X1=INT_MAX, X2=INT_MIN, Y1=INT_MAX, Y2=INT_MIN;
15         pii pt[4];
16         int sumarea = 0;
17         for(auto rec:rectangles) {
18             X1 = min(X1, min(rec[0], rec[2]));
19             Y1 = min(Y1, min(rec[1], rec[3]));
20             X2 = max(X2, max(rec[0], rec[2]));
21             Y2 = max(Y2, max(rec[1], rec[3]));
22             pt[0] = {rec[0], rec[1]};
23             pt[1] = {rec[2], rec[3]};
24             pt[2] = {rec[0], rec[3]};
25             pt[3] = {rec[2], rec[1]};
26             for(auto p:pt) {
27                 if(!ps.insert(toString(p)).second) ps.erase(toString(p));
28             }
29             sumarea += (rec[3]-rec[1])*(rec[2]-rec[0]);
30         }
31         if(ps.size()!=4) return false;
32         if(!ps.count(toString({X1,Y1}))) return false;
33         if(!ps.count(toString({X1,Y2}))) return false;
34         if(!ps.count(toString({X2,Y1}))) return false;
35         if(!ps.count(toString({X2,Y2}))) return false;
36         if(sumarea != (X2-X1)*(Y2-Y1)) return false;
37         return true;
38     }
39 };