問題
Find the total area covered by two rectilinear rectangles in a 2D plane.
Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.
Assume that the total area is never beyond the maximum possible value of int.
例子
-2 -2 2 2 -2 -2 2 2
16
分析
- 方法一：首先判斷兩個(gè)矩形是否相交。如果相交，總面積就是兩個(gè)矩形的面積和；如果不相交宝剖，總面積等于兩個(gè)矩形的面積和-重疊部分的面積聂抢；
- 方法二：通過min max函數(shù)直接求出重疊部分的面積，當(dāng)矩形不相交時(shí)，重疊面積為0观话。
要點(diǎn)
分情況討論=>歸一化為一種情況
時(shí)間復(fù)雜度
O(1)
空間復(fù)雜度
O(1)
代碼
方法一
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int total = (C - A) * (D - B) + (G - E) * (H - F);
if (C <= E || G <= A || D <= F || H <= B) return total;
vector<int> x{A, C, E, G};
vector<int> y{B, D, F, H};
sort(x.begin(), x.end());
sort(y.begin(), y.end());
int intersection = (x[2] - x[1]) * (y[2] - y[1]);
return total - intersection;
}
};
方法二
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int left = max(A, E), right = max(min(C, G), left); // 當(dāng)兩矩形不相交時(shí)，right = left
int bottom = max(B, F), top = max(min(D, H), bottom); // 當(dāng)兩矩形不相交時(shí)越平，top = bottom
return (C - A) * (D - B) + (G - E) * (H - F) - (right - left) * (top - bottom);
}
};
