Day 123-Q3 | ミンコフスキー和（Minkowski Sum）

問題

2つの凸多角形 $P$（$n$頂点、反時計回り、整数座標）と $Q$（$m$頂点、反時計回り、整数座標）が与えられる。ミンコフスキー和 $P \oplus Q = \{p+q \mid p\in P, q\in Q\}$ は凸多角形になることが知られている。この凸多角形の面積の2倍（整数値保証）を出力せよ。

入力形式

n
x_1 y_1
...
x_n y_n
m
x_1 y_1
...
x_m y_m

制約

$3 \le n, m \le 100000$

$|x_i|, |y_i| \le 10^8$

ともにCCWの厳密な凸多角形

3点が一直線に並ばない

入出力例

入力例1

出力例1

三角形を単位正方形で膨らませた五角形、面積7の2倍

概念図: 辺ベクトルの角度マージ

ヒント（段階的開示）

ヒント1: 方向性

$n\times m$通りの点の凸包を取るとO(nm log(nm))かかり間に合わない。凸多角形同士のミンコフスキー和には、凸包計算より遥かに速い専用アルゴリズムが存在する。

ヒント2: アプローチ

凸多角形をCCWで一周する辺ベクトルの角度は単調に増加する。2つの凸多角形の辺ベクトルを角度でソートしたまま1つにマージする（マージソートのマージ操作と同じ発想）と、それがそのまま$P\oplus Q$の辺ベクトル列になる。

ヒント3: 誘導（コード骨格）

角度が完全に一致する（外積0）辺は足し合わせて1本にする。ただし外積0は「同じ方向」か「正反対（180°）」かの両方を含むので、先に上半分/下半分の大分類（half）で判定する必要がある。

def half(v):  # 角度[0,180)か[180,360)か
    x, y = v
    return 0 if (y > 0 or (y == 0 and x > 0)) else 1

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    P = []
    for _ in range(n):
        x = int(data[idx]); y = int(data[idx + 1]); idx += 2
        P.append((x, y))
    m = int(data[idx]); idx += 1
    Q = []
    for _ in range(m):
        x = int(data[idx]); y = int(data[idx + 1]); idx += 2
        Q.append((x, y))

    def reorder(poly):
        start = 0
        for i in range(1, len(poly)):
            if (poly[i][1], poly[i][0]) < (poly[start][1], poly[start][0]):
                start = i
        return poly[start:] + poly[:start]

    P = reorder(P)
    Q = reorder(Q)

    def edges(poly):
        k = len(poly)
        return [(poly[(i + 1) % k][0] - poly[i][0],
                  poly[(i + 1) % k][1] - poly[i][1]) for i in range(k)]

    Pe = edges(P)
    Qe = edges(Q)

    def half(v):
        x, y = v
        return 0 if (y > 0 or (y == 0 and x > 0)) else 1

    def cross(a, b):
        return a[0] * b[1] - a[1] * b[0]

    merged = []
    i = j = 0
    while i < len(Pe) and j < len(Qe):
        ha, hb = half(Pe[i]), half(Qe[j])
        if ha != hb:
            if ha < hb:
                merged.append(Pe[i]); i += 1
            else:
                merged.append(Qe[j]); j += 1
            continue
        c = cross(Pe[i], Qe[j])
        if c > 0:
            merged.append(Pe[i]); i += 1
        elif c < 0:
            merged.append(Qe[j]); j += 1
        else:
            merged.append((Pe[i][0] + Qe[j][0], Pe[i][1] + Qe[j][1]))
            i += 1; j += 1
    while i < len(Pe):
        merged.append(Pe[i]); i += 1
    while j < len(Qe):
        merged.append(Qe[j]); j += 1

    sx, sy = P[0][0] + Q[0][0], P[0][1] + Q[0][1]
    verts = [(sx, sy)]
    for dx, dy in merged:
        px, py = verts[-1]
        verts.append((px + dx, py + dy))
    verts.pop()

    area2 = 0
    k = len(verts)
    for i in range(k):
        x1, y1 = verts[i]
        x2, y2 = verts[(i + 1) % k]
        area2 += x1 * y2 - x2 * y1

    print(area2)

solve()

計算量: 開始点探索O(n+m)、辺マージO(n+m)、面積計算O(n+m)。全体O(n+m)。三角形(0,0)(2,0)(0,2)と正方形(0,0)(1,0)(1,1)(0,1)の例を手作業でマージし、五角形(0,0)(3,0)(3,1)(1,3)(0,3)（面積2倍=14）が得られることを確認済み。全辺の合計が(0,0)に戻ること（閉多角形）、隣接辺の外積がすべて正（CCW凸性）であることも確認した。

Step-by-Step 解説

1なぜ辺ベクトルのマージで求まるか
ある角度方向のP⊕Qの最遠点は「Pの最遠点+Qの最遠点」になる。角度を連続回転させたときの切り替わりは、PかQのどちらかの辺の角度を通過するタイミングと一致する。

2開始点をそろえる理由
「y最小・x最小」の頂点から辿ると辺ベクトルの角度が-90°付近から270°付近まで単調増加しラップアラウンドしない。これがマージ比較（外積の符号のみ）を成立させる前提。

3角度が一致する辺の合体
外積0は「同じ方向」だけでなく「正反対（180°）」も含む。haf関数で大まかな半円を先に判定することで、同じhalf内の外積0は本当に同じ向きと保証できる。

4頂点列の復元と面積計算
開始点の和から辺ベクトルを順に足し合わせ頂点列を復元。シューレースの公式（整数演算のみ）で面積の2倍を求める。

5正しさの検証
入力例を手作業でマージ・頂点復元・面積計算し、五角形と面積2倍=14が得られることを確認した。

よくあるミス

ミス	原因	正しい書き方
外積0を無条件に同じ方向として合体する	180°反対向きも外積0になることを見落とす	halfで大分類してから同じ半分内でのみ外積比較する
開始点を揃えずにそのまま辺を作る	元の頂点順がy最小から始まるとは限らない	必ずy最小・x最小の頂点から順序を作り直す
面積を実数で計算し誤差が出る	座標が大きい場合の浮動小数点誤差蓄積	シューレースの公式は整数演算のみで完結する
頂点列の最後の重複除去を忘れる	辺を全部足すと開始点に戻ることを考慮していない	verts.pop()などで最後の重複点を除く

次のステップ

発展: ミンコフスキー和はロボットの経路計画（C-space obstacle）や凸多角形同士の衝突判定（GJKアルゴリズムの前段）の基礎。凸でない多角形の場合は凸分解してから個別に計算する。
次回予告: 森上のリンク操作による最大独立集合の動的維持

自己評価

完全理解おおむね理解要復習

Day 123-Q3 — ミンコフスキー和（Minkowski Sum）

問題