Day 080-Q2 — 凸多角形の Minkowski 差（形状縮小・内側オフセット計算）

問題

$N$ 頂点の凸多角形 $P$ と $M$ 頂点の凸多角形 $Q$（いずれも反時計回り）が与えられる。

Minkowski 差 $P \ominus Q = \{x \mid x + Q \subseteq P\}$ の面積を求めよ。

$P \ominus Q$ が空集合のときは 0 を出力すること。

入出力例

4
0 0
4 0
4 4
0 4
3
0 0
1 0
0 1

4.500000

概念図: Minkowski 差の幾何的解釈

ヒント

# Minkowski 差: -Q を作る
neg_Q = [(-x, -y) for x, y in Q]
# neg_Q を凸包にして反時計回りに整列

# Minkowski 和の辺マージ（偏角比較）
def edge(poly, i):
    n = len(poly)
    return (poly[(i+1)%n][0]-poly[i][0],
            poly[(i+1)%n][1]-poly[i][1])

c = ep[0]*eq[1] - ep[1]*eq[0]  # 外積で偏角比較
if c > 0: # ep が先  → ep を追加, i++
elif c < 0: # eq が先 → eq を追加, j++
else: # 同偏角 → 両方追加, i++, j++

模範解答

import sys
input = sys.stdin.readline

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

def convex_hull(pts):
    pts = sorted(set(pts))
    if len(pts) <= 1: return pts
    lower, upper = [], []
    for p in pts:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    for p in reversed(pts):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

def polygon_area(poly):
    n = len(poly)
    s = sum(poly[i][0]*poly[(i+1)%n][1] - poly[(i+1)%n][0]*poly[i][1]
            for i in range(n))
    return abs(s) / 2

def reorder_ccw(poly):
    n = len(poly)
    start = min(range(n), key=lambda i: (poly[i][1], poly[i][0]))
    return poly[start:] + poly[:start]

def minkowski_sum(P, Q):
    def edge(poly, i):
        n = len(poly)
        return (poly[(i+1)%n][0]-poly[i][0], poly[(i+1)%n][1]-poly[i][1])
    n, m = len(P), len(Q)
    i = j = 0
    result = [(P[0][0]+Q[0][0], P[0][1]+Q[0][1])]
    while i < n or j < m:
        ep = edge(P, i % n) if i < n else (0, 0)
        eq = edge(Q, j % m) if j < m else (0, 0)
        c = ep[0]*eq[1] - ep[1]*eq[0]
        if i >= n: c = 1
        if j >= m: c = -1
        if c > 0:
            result.append((result[-1][0]+ep[0], result[-1][1]+ep[1]))
            i += 1
        elif c < 0:
            result.append((result[-1][0]+eq[0], result[-1][1]+eq[1]))
            j += 1
        else:
            result.append((result[-1][0]+ep[0]+eq[0], result[-1][1]+ep[1]+eq[1]))
            i += 1; j += 1
    result.pop()
    return result

def main():
    N = int(input())
    P = [tuple(map(int, input().split())) for _ in range(N)]
    M = int(input())
    Q = [tuple(map(int, input().split())) for _ in range(M)]

    neg_Q = [(-x, -y) for x, y in Q]
    neg_Q_hull = convex_hull(neg_Q)

    if len(neg_Q_hull) < 3:
        print(0)
        return

    P2 = reorder_ccw(convex_hull(P))
    nQ = reorder_ccw(neg_Q_hull)
    diff = minkowski_sum(P2, nQ)
    hull = convex_hull(diff)

    if len(hull) < 3:
        print(0)
    else:
        print(f"{polygon_area(hull):.6f}")

main()

Step-by-Step 解説

Step 1: Minkowski 差の定義確認

$$P \ominus Q = \{x \in \mathbb{R}^2 \mid x + Q \subseteq P\}$$

「$Q$ を置いたとき、全体が $P$ に収まるような中心点の集合」と理解できる。

Step 2: $-Q$ の凸包

$Q$ の各頂点を原点対称 $(-x, -y)$ にして凸包を取る。これが Minkowski 差計算の中間オブジェクト。

Step 3: Minkowski 和の辺マージ

二つの凸多角形の辺ベクトルを 偏角の昇順 にマージして、結果の多角形の辺列を構築する。外積の符号で偏角の大小を判定するのがポイント。

Step 4: 開始点の選択

底点（y 最小 → x 最小）から出発しないとマージが正しく動作しない。reorder_ccw で底点を先頭に揃える。

Step 5: 面積計算

Shoelace 公式: $$A = \frac{1}{2}\left|\sum_{i}(x_i y_{i+1} - x_{i+1} y_i)\right|$$

よくあるミス

次のステップ

• 発展問題: 凸多角形の平行移動最大距離（Minkowski 和の直径）
• 関連: 衝突判定（GJK アルゴリズム）— ロボット工学での応用

自己評価