問題
二次元平面上に $N$ 個の矩形 $R_i = (x1_i, y1_i, x2_i, y2_i)$（左下・右上の座標）が与えられる。これらの矩形の和集合の面積を求めよ。
座標の値は最大 $10^9$ だが、矩形数 $N \le 2000$ であるため座標圧縮を行い $O(N^2)$ で処理せよ。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N$ | $1 \le N \le 2000$ | 矩形数 |
| $x1_i, x2_i$ | $0 \le x1_i < x2_i \le 10^9$ | 横座標 |
| $y1_i, y2_i$ | $0 \le y1_i < y2_i \le 10^9$ | 縦座標 |
入出力例
入力例1
3
0 0 4 4
2 2 6 6
3 0 7 5出力例1
44入力例2
2
0 0 10 10
3 3 7 7出力例2
100概念図: 座標圧縮と格子セルへの分割
ヒント
ヒント1（方向性）
座標圧縮を行い、各セルの幅と高さを計算する。圧縮後の格子の各セルについて「何個の矩形がそのセルを覆っているか」を判定し、1以上なら面積に加算する。$N$ 個の矩形から最大 $2N$ 個の $x$ 座標・$2N$ 個の $y$ 座標が生まれ、格子は $O(N) \times O(N)$ サイズ。
ヒント2（アプローチ）
手順: (1) $x$ 座標・$y$ 座標を別々に圧縮（重複排除・ソート） (2) 各矩形を圧縮後格子インデックスに変換 (3) 2D 差分配列で被覆回数を管理 (4) 前処理で累積和を取り、各セルの被覆回数を確定 (5) 被覆回数 > 0 のセルの実座標面積を合計する
ヒント3（ほぼ答え）
xs = sorted(set(x for r in rects for x in (r[0], r[2])))
ys = sorted(set(y for r in rects for y in (r[1], r[3])))
xi = {v: i for i, v in enumerate(xs)}
yi = {v: i for i, v in enumerate(ys)}
# 2D 差分配列
diff = [[0] * len(ys) for _ in range(len(xs))]
for x1, y1, x2, y2 in rects:
ix1, ix2 = xi[x1], xi[x2]
iy1, iy2 = yi[y1], yi[y2]
diff[ix1][iy1] += 1
diff[ix2][iy1] -= 1
diff[ix1][iy2] -= 1
diff[ix2][iy2] += 1
# 累積和で各セルの被覆回数を求める
# ... そして被覆セルの面積を合計模範解答
import sys
input = sys.stdin.readline
def solve():
N = int(input())
rects = []
for _ in range(N):
x1, y1, x2, y2 = map(int, input().split())
rects.append((x1, y1, x2, y2))
xs = sorted(set(x for r in rects for x in (r[0], r[2])))
ys = sorted(set(y for r in rects for y in (r[1], r[3])))
xi = {v: i for i, v in enumerate(xs)}
yi = {v: i for i, v in enumerate(ys)}
Mx, My = len(xs), len(ys)
# 2D 差分配列
diff = [[0] * My for _ in range(Mx)]
for x1, y1, x2, y2 in rects:
ix1, ix2 = xi[x1], xi[x2]
iy1, iy2 = yi[y1], yi[y2]
diff[ix1][iy1] += 1
diff[ix2][iy1] -= 1
diff[ix1][iy2] -= 1
diff[ix2][iy2] += 1
# 2D 前置和 (y方向)
for i in range(Mx):
for j in range(1, My):
diff[i][j] += diff[i][j-1]
# 2D 前置和 (x方向)
for j in range(My):
for i in range(1, Mx):
diff[i][j] += diff[i-1][j]
total = 0
for i in range(Mx - 1):
for j in range(My - 1):
if diff[i][j] > 0:
total += (xs[i+1] - xs[i]) * (ys[j+1] - ys[j])
print(total)
solve()Step-by-Step 解説
Step 1: 座標圧縮の仕組み
$N$ 個の矩形から最大 $2N$ 個の $x$ 座標が生まれる。これらでグリッドを分割すると、各セルは完全に「特定の矩形に覆われているか否か」が決まる。
xs = sorted(set(x for r in rects for x in (r[0], r[2])))
# セル [i] の幅 = xs[i+1] - xs[i]Step 2: 差分配列による被覆カウント
| 操作 | 意味 |
|---|---|
diff[ix1][iy1] += 1 | 矩形の左下を+1 |
diff[ix2][iy1] -= 1 | 右端で-1 |
diff[ix1][iy2] -= 1 | 上端で-1 |
diff[ix2][iy2] += 1 | 右上で+1（引きすぎた分の補正） |
2D 累積和を取ると各セルの被覆回数が得られる。
Step 3: 計算量
| 操作 | 計算量 |
|---|---|
| 座標圧縮 | $O(N \log N)$ |
| 差分配列の構築 | $O(N)$ |
| 2D 累積和 | $O(N^2)$ |
| 面積計算 | $O(N^2)$ |
| 合計 | $O(N^2)$ |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| セル数の誤り | $2N$ 座標で $2N-1$ セル | range(len(xs) - 1) でループ |
| 差分配列の4点更新忘れ | 矩形の包除が正しくない | 4隅を±1 で更新 |
| 整数オーバーフロー | 座標 $10^9$、面積は $10^{18}$ になりえる | Python は自動 big int だが C++ では long long |
次のステップ
- 発展問題: 矩形の和集合面積（スウィープ + セグメント木 $O(N^2 \log N)$）
- 発展問題: $N \le 10^5$ の場合（スウィープライン + 区間加算/カウント SegTree）
自己評価
理解度: / /
自分の回答:
気づき・メモ: