C++で解く長方形エリアII ― 座標圧縮と走査線法による被覆面積の計算

問題概要

軸に平行な長方形のリストが与えられるものとします。各 rectangle[i] = {x1, y1, x2, y2} において、(x1, y1) は i 番目の長方形の左下隅の座標、(x2, y2) は右上隅の座標を表します。

求めたいのは、平面上でこれらすべての長方形が覆っている領域の合計面積です。答えは非常に大きな値になる可能性があるため、10⁹ + 7 で割った余りを返すことになっています。

たとえば、入力が次のような場合を考えてみましょう。

このとき、出力は 6 となります。

解法の方針：座標圧縮＋走査線（スイープライン）

この問題は、座標圧縮（座標の離散化）と走査線法（スイープライン法）を組み合わせることで効率的に解けます。基本的なアイデアは次のとおりです。

• すべての長方形の x 座標（左端と右端）を集めてソートし、重複を除去することで、x 軸をいくつかの小区間に分割します。
• 各長方形について、「下辺では区間カウントを +1」「上辺では -1」というイベントを生成し、y 座標順に並べ替えます。
• y の小さいほうから走査しながら、各区間に現在何個の長方形がかかっているか（count）を管理し、直前のイベントからの高さ (y − currentY) と、被覆されている区間の合計幅 sum を掛けた値を面積に加算していきます。

アルゴリズムの詳細手順

• m = 10^9 + 7 として定義します。
• 関数 add(a, b) を定義します。(a mod m) + (b mod m) を返します。
• 配列 xv を用意し、最初に {0} を追加します。
• i := 0 から v のサイズ未満の間、i を 1 ずつ増やしながら繰り返します。
  • v[i][0] と v[i][2] を xv の末尾に挿入します。
• xv をソートし、unique() で重複要素を削除します。
• マップ index を定義し、圧縮後の各 x 座標に連番のインデックスを割り当てます。
• index のサイズと同じ大きさの配列 count を用意します（各区間の被覆数を記録するため）。
• 2 次元配列 x を用意し、i := 0 から v のサイズ未満の間、次を繰り返します。
  • x1 := v[i][0]、y1 := v[i][1]、x2 := v[i][2]、y2 := v[i][3] とします。
  • { y1, x1, x2, 1 }（下辺イベント）と { y2, x1, x2, -1 }（上辺イベント）を x に挿入します。
• x を y 座標順にソートします。
• ret := 0、sum := 0、currentY := 0 で初期化します。
• i := 0 から x のサイズ未満の間、次を繰り返します。
  • y := x[i][0]、x1 := x[i][1]、x2 := x[i][2]、sig := x[i][3] を取得します。
  • ret := add(ret, (y − currentY) × sum) として、これまでの帯状領域の面積を加算します。
  • currentY := y と更新します。
  • i := index[x1] から index[x2] 未満まで、count[i] += sig で区間のカウントを更新します。
  • sum を 0 に戻し、count[i] > 0 となるすべての i について sum += (xv[i+1] − xv[i]) を加算し、現在有効な区間の合計幅を再計算します。
• 最後に ret mod m を返します。

それでは、実際の実装を見て理解を深めましょう。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
   public:
   lli add(lli a, lli b){
      return ((a % m) + (b % m) % m);
   }
   map<int, int> compress(vector<vector<int> >& v){
      vector<int> temp;
      for (int i = 0; i < v.size(); i++) {
         temp.push_back(v[i][0]);
         temp.push_back(v[i][2]);
      }
      sort(temp.begin(), temp.end());
      map<int, int> ret;
      int idx = 0;
      for (int i = 0; i < temp.size(); i++) {
         if (!ret.count(temp[i])) {
            ret[temp[i]] = idx;
            idx++;
         }
      }
      return ret;
   }
   int rectangleArea(vector<vector<int> >& v){
      vector<int> xv;
      xv.push_back({ 0 });
      for (int i = 0; i < v.size(); i++) {
         xv.push_back(v[i][0]);
         xv.push_back(v[i][2]);
      }
      sort(xv.begin(), xv.end());
      vector<int>::iterator uniItr = unique(xv.begin(), xv.end());
      xv.erase(uniItr, xv.end());
      map<int, int> index;
      int idx = 0;
      for (int i = 0; i < xv.size(); i++) {
         index[xv[i]] = i;
      }
      vector<int> count(index.size());
      vector<vector<int> > x;
      int x1, x2, y1, y2;
      for (int i = 0; i < v.size(); i++) {
         x1 = v[i][0];
         y1 = v[i][1];
         x2 = v[i][2];
         y2 = v[i][3];
         x.push_back({ y1, x1, x2, 1 });
         x.push_back({ y2, x1, x2, -1 });
      }
      sort(x.begin(), x.end());
      lli ret = 0;
      lli sum = 0, currentY = 0;
      for (int i = 0; i < x.size(); i++) {
         lli y = x[i][0];
         x1 = x[i][1];
         x2 = x[i][2];
         int sig = x[i][3];
         ret = add(ret, (y - currentY) * sum);
         currentY = y;
         for (int i = index[x1]; i < index[x2]; i++) {
            count[i] += sig;
         }
         sum = 0;
         for (int i = 0; i < count.size(); i++) {
            if (count[i] > 0) {
               sum += (xv[i + 1] - xv[i]);
            }
         }
      }
      return ret % m;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,2,2},{1,0,2,3},{1,0,3,1}};
   cout << (ob.rectangleArea(v));
}

入力

{{0,0,2,2},{1,0,2,3},{1,0,3,1}}

出力

6

計算量とさらなる改善

長方形の数を n とすると、イベントのソートには O(n log n) かかり、さらに各イベント処理ごとに count 配列の更新と合計幅の再計算が最大 O(n) 行われるため、この実装全体の計算量は O(n²) となります。入力規模が大きい場合は、セグメント木（遅延伝播付き）を使って区間への加算と被覆幅の管理を高速化すれば、O(n log n) まで改善できるのが一般的です。