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.

Rectangle Area - 图1

Assume that the total area is never beyond the maximum possible value of int.

分析

简单平面几何。根据容斥原理：S(M ∪ N) = S(M) + S(N) - S(M ∩ N)，最关键的是求出相交部分的面积。

代码

  1. // Rectangle Area
  2. // Time Complexity: O(1), Space Complexity: O(1)
  3. public class Solution {
  4.     public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
  5.         final int area = (C - A) * (D- B) + (G - E) * (H - F);
  6.         // prevent overflow
  7.         if (C < E || G < A || D < F || H < B) return area;
  8.         final int intersection = Math.max(Math.min(C, G) - Math.max(A, E), 0) *
  9.                 Math.max(Math.min(D, H) - Math.max(B, F), 0);
  10.         return area - intersection;
  11.     }
  12. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/simulation/rectangle-area.html