223. Rectangle Area

问题

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

分析

• 方法一：首先判断两个矩形是否相交。如果相交，总面积就是两个矩形的面积和；如果不相交，总面积等于两个矩形的面积和-重叠部分的面积；
• 方法二：通过min max函数直接求出重叠部分的面积，当矩形不相交时，重叠面积为0。

要点

分情况讨论=>归一化为一种情况

时间复杂度

O(1)

空间复杂度

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); // 当两矩形不相交时，right = left
        int bottom = max(B, F), top = max(min(D, H), bottom); // 当两矩形不相交时，top = bottom
        return (C - A) * (D - B) + (G - E) * (H - F) - (right - left) * (top - bottom);
    }
};