[LeetCode] 223. Rectangle Area

223. Rectangle Area

• Hardness: \(\color{orange}\textsf{Medium}\)
• Ralated Topics: Math、Geometry

一、題目

Given the coordinates of two rectilinear rectangles in a 2D plane, return the total area covered by the two rectangles. The first rectangle is defined by its bottom-left corner (ax1, ay1) and its top-right corner (ax2, ay2). The second rectangle is defined by its bottom-left corner (bx1, by1) and tis top-right corner (bx2, by2).

Example 1:

• Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
• Output: 45

Example 2:

• Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
• Output: 16

Constraints:

• -10^4 <= ax1 <= ax2 <= 10^4
• -10^4 <= ay1 <= ay2 <= 10^4
• -10^4 <= bx1 <= bx2 <= 10^4
• -10^4 <= by1 <= by2 <= 10^4

二、分析

• 矩形的面積為長寬相加，所以以題目所示，單個矩形的面積為 (x2-x1)*(y2-y1)，但此題需考慮到重疊的情形發生，需將重疊的部分額外扣掉。
• 兩個矩形重疊的小矩形的 bottom-left corner 為 (max(ax1,bx1),max(ay1,by1))，top-right corner 為 (min(ax2,bx2),min(ay2,by2))。
  • 但注意到當下列情形發生的時候，兩個矩形不發生重疊：cx1 >= cx2 || cy1 >= cy2。
• 為方便計算，將矩形寫成一個物件。

struct Rect {
    int x1,x2,y1,y2;
};

三、解題

1. Math

• Time complexity: \(O(1)\)
• Space complexity: \(O(1)\)

struct Rect {
    int x1,y1,x2,y2;
    Rect(int x1_, int y1_, int x2_, int y2_):x1(x1_),y1(y1_),x2(x2_),y2(y2_) {}
    int area() {
        return (x1 >= x2 || y1 >= y2) ? 0 : (x2 - x1) * (y2 - y1);      // 不重疊則回傳面積 0
    }
};
class Solution {
public:
    int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        Rect a(ax1,ay1,ax2,ay2);
        Rect b(bx1,by1,bx2,by2);
        Rect c(max(ax1,bx1),
                max(ay1,by1),
                min(ax2,bx2),
                min(ay2,by2));
        return a.area() + b.area() - c.area();
    }
};

回目錄 Catalog