Day 066-Q2 | 凸多角形最短距離・回転キャリパー法

問題

2つの凸多角形 $P$（頂点数 $N$）と $Q$（頂点数 $M$）が与えられる。両多角形が交差しない場合、2つの凸多角形間の最短距離を求めよ。交差する場合は $0$ を出力せよ。頂点は反時計回りに与えられる。

制約

パラメータ	範囲
$N, M$	$3 \le N, M \le 10^5$
座標	$-10^9 \le x_i, y_i \le 10^9$
形状	各多角形は厳密凸（3点共線なし）

入出力例

入力例 1（非交差）

出力例 1

2.000000000

入力例 2（交差）

出力例 2

0.000000000

概念図: 回転キャリパー法

ヒント（段階的開示）

ヒント1: 方向性

回転キャリパー法を2つの凸多角形間に適用する。各多角形の支持線（calipers）を同期回転させながら、辺-辺間の最短距離候補を収集する。凸性があるため N+M ステップで終わる。

ヒント2: アプローチ

各多角形の最下点（y最小、同値なら x最小）から初期化
各ステップで P の i 番辺ベクトルと Q の j 番辺ベクトルの外積を計算
外積 ≥ 0 なら P の pointer を進め、外積 ≤ 0 なら Q を進める
各ステップで現在の辺ペア間の最短距離（線分-線分距離）を更新

ヒント3: コード骨格

def rotating_calipers_dist(P, Q):
    n, m = len(P), len(Q)
    pi = min(range(n), key=lambda i: (P[i][1], P[i][0]))
    qi = min(range(m), key=lambda i: (Q[i][1], Q[i][0]))
    min_dist = float('inf')
    for _ in range(n + m + 2):
        p1, p2 = P[pi], P[(pi+1)%n]
        q1, q2 = Q[qi], Q[(qi+1)%m]
        d = seg_dist_sq(p1, p2, q1, q2)
        min_dist = min(min_dist, d)
        ep = (p2[0]-p1[0], p2[1]-p1[1])
        eq = (q2[0]-q1[0], q2[1]-q1[1])
        c = ep[0]*eq[1] - ep[1]*eq[0]
        if c >= 0: pi = (pi+1) % n
        if c <= 0: qi = (qi+1) % m
    return min_dist ** 0.5

模範解答 (Python)

import sys
from math import sqrt
input = sys.stdin.readline

EPS = 1e-9

def seg_dist_sq(a, b, c, d):
    def seg_pt_sq(p, q, r):
        pq = (q[0]-p[0], q[1]-p[1])
        denom = pq[0]**2 + pq[1]**2
        if denom < EPS:
            dx, dy = r[0]-p[0], r[1]-p[1]
            return dx*dx + dy*dy
        t = max(0.0, min(1.0, ((r[0]-p[0])*pq[0]+(r[1]-p[1])*pq[1]) / denom))
        dx = r[0]-p[0]-t*pq[0]; dy = r[1]-p[1]-t*pq[1]
        return dx*dx+dy*dy
    def cross(o, u, v):
        return (u[0]-o[0])*(v[1]-o[1]) - (u[1]-o[1])*(v[0]-o[0])
    d1 = cross(c,d,a); d2 = cross(c,d,b)
    d3 = cross(a,b,c); d4 = cross(a,b,d)
    if ((d1 > 0) != (d2 > 0)) and ((d3 > 0) != (d4 > 0)):
        return 0.0
    return min(seg_pt_sq(a,b,c), seg_pt_sq(a,b,d),
               seg_pt_sq(c,d,a), seg_pt_sq(c,d,b))

def convex_polygon_dist(P, Q):
    n, m = len(P), len(Q)
    pi = min(range(n), key=lambda i: (P[i][1], P[i][0]))
    qi = min(range(m), key=lambda i: (Q[i][1], Q[i][0]))
    min_dist_sq = float('inf')
    for _ in range(n + m + 2):
        p1, p2 = P[pi], P[(pi+1)%n]
        q1, q2 = Q[qi], Q[(qi+1)%m]
        d = seg_dist_sq(p1, p2, q1, q2)
        if d < min_dist_sq:
            min_dist_sq = d
        ep = (p2[0]-p1[0], p2[1]-p1[1])
        eq = (q2[0]-q1[0], q2[1]-q1[1])
        c = ep[0]*eq[1] - ep[1]*eq[0]
        if c >= 0:
            pi = (pi+1) % n
        if c <= 0:
            qi = (qi+1) % m
    return sqrt(min_dist_sq)

def solve():
    def read_poly():
        n = int(input())
        return [tuple(map(int, input().split())) for _ in range(n)]
    P = read_poly()
    Q = read_poly()
    dist = convex_polygon_dist(P, Q)
    print(f"{dist:.9f}")

solve()

Step-by-Step 解説

Step 1: 問題の設定

2つの凸多角形の距離 = 各多角形の辺と相手の頂点（または辺）の最短距離のうちの最小値。凸性があるため、辺を「同期回転」させながら候補を絞れる。

Step 2: 初期化

両多角形の最下点（y最小、同値なら x最小）から開始。回転キャリパーの「0度方向」に対応する。

Step 3: 回転ステップ

各ステップで P の $i$ 番辺ベクトル $\vec{e_P}$ と Q の $j$ 番辺ベクトル $\vec{e_Q}$ の外積を計算。外積 $\ge 0$ なら P の caliper を進め、$\le 0$ なら Q を進め、$= 0$ なら両方進める。N+M ステップで一周。

Step 4: 線分-線分距離

各ステップで現在の辺ペア間の最短距離（線分-線分距離）を計算。交差する場合は 0。線分-線分距離は各頂点から相手の辺への垂線の足を求めて計算する。

Step 5: 計算量

処理	計算量
底点探索	$O(N+M)$
回転ループ	$O(N+M)$ ステップ
線分距離計算（各ステップ）	$O(1)$
全体	$O(N+M)$

よくあるミス

ミス	原因	正しい書き方
外積の符号で進む方向を逆にする	外積の方向定義の勘違い	cross(ep,eq) ≥ 0 → P 進める
線分交差時の 0 を見落とす	距離が 0 の特殊ケース	線分交差判定を含める
始点の設定が最下点でなく index 0	回転が正しく機能しない	`bottom()` で y最小点を取得

次のステップ

発展問題: 2つの凸多角形間の「最短接近パス」（平行移動で衝突する直前の距離と方向）を Minkowski 差と GJK アルゴリズムで O(N+M) で求めよ。

自己評価

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