题目描述

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.

 

题目大意

求两个矩形占的面积的和（重叠部分不能重复计算）。

 

示例

E1

Input: A = -3, B = 0, C = 3, D = 4, E = 0, F = -1, G = 9, H = 2
Output: 45

 

解题思路

被LeetCode@rich巧妙的算法惊到了，之前还苦苦的ifelse与这行代码一比真是愚蠢之极(╯°Д°)╯︵ ┻━┻ 。

该算法主要思路是若两个矩形出现重叠，只需得知重叠部分矩形的两个顶点坐标即可，无需判断是哪个矩形的哪个顶点，将所有顶点排序之后取中间的两个顶点后就是重叠部分的矩形顶点坐标。

 

复杂度分析

时间复杂度：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) {
        // 避免出现越界现象将结果设为long long
        long long res = (long long)(C - A) * (long long)(D - B) + (long long)(G - E) * (long long)(H - F);
        // 若矩形之间无重叠部分直接返回两矩形面积之和
        if(C <= E || A >= G || D <= F || B >= H)
            return res;
        // 将四个顶点按从小到大的顺序排序，排序后的中间两个位置就是重叠部分的坐标， 
        // 可根据上面图片进行分析理解
        vector<int> h;
        vector<int> v;
        h.push_back(A);
        h.push_back(C);
        h.push_back(E);
        h.push_back(G);
        
        v.push_back(B);
        v.push_back(D);
        v.push_back(F);
        v.push_back(H);
        
        sort(h.begin(), h.end());
        sort(v.begin(), v.end());
        
        return res - (h[2] - h[1]) * (v[2] - v[1]);
    }
};