Day 074-Q3 — Minkowski 和（凸多角形の合成・面積計算・内外判定 O(log N)）

問題

平面上に2つの凸多角形 $P$（$N$ 頂点）と $Q$（$M$ 頂点）が与えられる（反時計回り）。これらの Minkowski 和 $P \oplus Q = \{p + q \mid p \in P, q \in Q\}$ の面積を求めよ。

さらに $T$ 個のクエリが来る。各クエリは点 $v = (x, y)$ について、$v$ が $P \oplus Q$ の内部または境界に含まれるかを判定せよ。

入出力例

4
0 0
2 0
2 2
0 2
4
0 0
1 0
1 1
0 1
T 0

9.000000000

概念図: Minkowski 和の辺マージ

ヒント

def minkowski_sum(P, Q):
    def bot(poly):
        return min(range(len(poly)), key=lambda i: (poly[i][1], poly[i][0]))
    def edges(poly):
        n = len(poly)
        return [(poly[(i+1)%n][0]-poly[i][0], poly[(i+1)%n][1]-poly[i][1])
                for i in range(n)]
    def vcross(a, b):
        return a[0]*b[1] - a[1]*b[0]

    si, sj = bot(P), bot(Q)
    P, Q = P[si:]+P[:si], Q[sj:]+Q[:sj]
    ep, eq = edges(P), edges(Q)
    result = [(P[0][0]+Q[0][0], P[0][1]+Q[0][1])]
    i = j = 0
    while i < len(ep) or j < len(eq):
        if i >= len(ep):
            e = eq[j]; j += 1
        elif j >= len(eq):
            e = ep[i]; i += 1
        else:
            c = vcross(ep[i], eq[j])
            if c > 0:   e = ep[i]; i += 1
            elif c < 0: e = eq[j]; j += 1
            else:        e = (ep[i][0]+eq[j][0], ep[i][1]+eq[j][1]); i += 1; j += 1
        result.append((result[-1][0]+e[0], result[-1][1]+e[1]))
    result.pop()
    return result

模範解答

import sys
input = sys.stdin.readline

def shoelace(poly):
    n = len(poly)
    s = 0
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i+1)%n]
        s += x1*y2 - x2*y1
    return abs(s) / 2

def minkowski_sum(P, Q):
    def bot(poly):
        return min(range(len(poly)), key=lambda i: (poly[i][1], poly[i][0]))
    def edges(poly):
        n = len(poly)
        return [(poly[(i+1)%n][0]-poly[i][0], poly[(i+1)%n][1]-poly[i][1])
                for i in range(n)]
    def vcross(a, b):
        return a[0]*b[1] - a[1]*b[0]

    si, sj = bot(P), bot(Q)
    P, Q = P[si:]+P[:si], Q[sj:]+Q[:sj]
    ep, eq = edges(P), edges(Q)
    result = [(P[0][0]+Q[0][0], P[0][1]+Q[0][1])]
    i = j = 0
    while i < len(ep) or j < len(eq):
        if i >= len(ep):
            e = eq[j]; j += 1
        elif j >= len(eq):
            e = ep[i]; i += 1
        else:
            c = vcross(ep[i], eq[j])
            if c > 0:
                e = ep[i]; i += 1
            elif c < 0:
                e = eq[j]; j += 1
            else:
                e = (ep[i][0]+eq[j][0], ep[i][1]+eq[j][1])
                i += 1; j += 1
        result.append((result[-1][0]+e[0], result[-1][1]+e[1]))
    result.pop()
    return result

def point_in_convex_polygon(poly, px, py):
    n = len(poly)
    ox, oy = poly[0]
    def cr(ax, ay, bx, by):
        return ax*by - ay*bx
    dx, dy = px - ox, py - oy
    c1 = cr(poly[1][0]-ox, poly[1][1]-oy, dx, dy)
    cn = cr(poly[n-1][0]-ox, poly[n-1][1]-oy, dx, dy)
    if c1 < 0 or cn > 0:
        return False
    lo, hi = 1, n - 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if cr(poly[mid][0]-ox, poly[mid][1]-oy, dx, dy) >= 0:
            lo = mid
        else:
            hi = mid
    c = cr(poly[lo+1][0]-poly[lo][0], poly[lo+1][1]-poly[lo][1],
            px-poly[lo][0], py-poly[lo][1])
    return c >= 0

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

    mink = minkowski_sum(P, Q_poly)
    area = shoelace(mink)
    print(f"{area:.9f}")

    line = input().strip().split()
    T = int(line[-1])
    for _ in range(T):
        qx, qy = map(int, input().split())
        print("Yes" if point_in_convex_polygon(mink, qx, qy) else "No")

solve()

Step-by-Step 解説

Step 1: Minkowski 和の性質

$P \oplus Q$ は凸多角形。辺ベクトルは $P$ と $Q$ の辺ベクトルを偏角ソートでマージしたもの。頂点数は最大 $N + M$。

Step 2: 最下点からのスタート

両方の最下点（$y$ 最小 → $x$ 最小）を求め、それを Minkowski 和の出発点にする。出発点は $\text{start}(P) + \text{start}(Q)$。

Step 3: 辺のマージ

外積 vcross(ep[i], eq[j]) が正 → P の辺が偏角的に小さい、負 → Q の辺が小さい、0 → 同偏角（両方進め、辺ベクトルを加算）。

Step 4: 内外判定 O(log N)

凸多角形の内外判定は O(log N)。基点 poly[0] として三角形ファンを作り、二分探索で対応する三角形を特定し cross product の符号を確認する。

よくあるミス

次のステップ

• 発展問題: $K$ 個の凸多角形の Minkowski 和（全辺をマージ）
• 類題: 「2つの凸多角形の衝突判定」→ Minkowski 差 $P \ominus Q$
• 応用: 射影 Minkowski 和 → 線形計画の実行可能領域

自己評価