C++で2つの長方形が覆う合計面積を求めるアルゴリズム

2次元平面上に置かれた2つの軸に平行な長方形について、それらが覆う領域の合計面積を求める問題を考えます。各長方形は、左下の頂点と右上の頂点の座標によって定義されます。下図のように、第1の長方形は左下 (A, B)・右上 (C, D)、第2の長方形は左下 (E, F)・右上 (G, H) として表されます。

解き方のアプローチ

この問題を解くための手順は以下の通りです。

• まず、2つの長方形が重なっているかどうかを判定します。C ≤ E、A ≥ G、B ≥ H、D ≤ F のいずれかが成り立つ場合、2つの長方形は重ならないため、それぞれの面積の和 (C − A) × (D − B) + (G − E) × (H − F) をそのまま返します。

• 重なる場合は、x座標である A, C, E, G を配列 h に、y座標である B, D, F, H を配列 v に格納します。

• 両方の配列をソートします。4つの座標を並べ替えると、中央の2つの値（h[1], h[2] および v[1], v[2]）が重なり部分のx方向・y方向の範囲に対応します。

• したがって、重なり部分の面積は temp = (h[2] − h[1]) × (v[2] − v[1]) として求められます。

• 最終的な答えは「長方形1の面積 ＋ 長方形2の面積 − 重なり部分の面積」です。これは集合の和を求める際に用いられる「包除原理」と同じ考え方です。単純に2つの面積を足すだけでは重なり部分が二重にカウントされてしまうため、その分を差し引く必要があります。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
       if(C <= E || A >= G || B >= H || D <= F) return (C - A) * (D - B) + (G - E) * (H - F);
       vector <int> h;
       h.push_back(A);
       h.push_back(C);
       h.push_back(E);
       h.push_back(G);
       vector <int> v;
       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());
       long long int temp = (h[2] - h[1]) * (v[2] - v[1]);
       long long int total = - temp;
       total += (C - A) * (D - B);
       total += (G - E) * (H - F);
       return total;
    }
};
main(){
    Solution ob;
    cout << (ob.computeArea(-3, 0, 3, 4, 0, -1, 9, 2));
}

入力

-3
0
3
4
0
-1
9
2

出力

45

この例では、第1の長方形が (-3, 0)〜(3, 4)、第2の長方形が (0, -1)〜(9, 2) に配置されており、両者の重なり部分を除いた合計面積 45 が正しく求められています。計算量は座標のソートが支配的となるため O(1)（要素数が固定の4つのため）とみなせ、非常に効率的な手法です。