leetcode筆記：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.

二. 題目分析

題目大意很簡單，即計算二維平面上兩個矩形的覆寫面積。兩矩形通過其左下和右上的坐标進行定義。假設總面積不會超過int的最大值。

根據常用的幾何知識可以很快解決這個問題。假設兩個矩形分别為

A, B

，

Area(A ∪ B)

表示由兩個矩形加起來的覆寫面積，則有以下公式：

Area(A ∪ B) = Area(A) + Area(B) - Area(A ∩ B)

三. 示例代碼

// C++ 代碼
class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int rectangle1 = (C - A) * (D - B);
        int rectangle2 = (G - E) * (H - F);
        // 以下是兩個矩陣相交部分的上下左右坐标
        int left = max(A, E), right = min(C, G), top = min(D, H), bottom = max(B, F);
        if (right <= left || top <= bottom) return rectangle1 + rectangle2;
        return rectangle1 + rectangle2 - (right - left) * (top - bottom);
    }
};
           

// Python 代碼
class Solution:
    # @param {integer} A
    # @param {integer} B
    # @param {integer} C
    # @param {integer} D
    # @param {integer} E
    # @param {integer} F
    # @param {integer} G
    # @param {integer} H
    # @return {integer}
    def computeArea(self, A, B, C, D, E, F, G, H):
        sums = (C - A) * (D - B) + (G - E) * (H - F)
        return sums - max(min(C, G) - max(A, E), 0) * max(min(D, H) - max(B, F), 0)
           

四. 小結

實作算法時，需注意各下标的順序，避免出錯。