Day 073-Q3 — 凸多角形の接線・最近点クエリ（二分探索 + 回転キャリパー）

問題

$N$ 頂点の凸多角形（反時計回りに与えられる）と $Q$ 個の点クエリ $q_i = (x_i, y_i)$ が与えられる。

各クエリに対して、以下を答えよ：

1. 内外判定: 点 $q_i$ が凸多角形の内部（辺上を含む）にあるか外部にあるか
2. 最近点距離: 点 $q_i$ から凸多角形の境界までのユークリッド距離（内部の場合は 0）

入出力例

4 3
0 0
4 0
4 4
0 4
2 2
5 2
0 0

INSIDE 0.000000
OUTSIDE 1.000000
INSIDE 0.000000

概念図: 扇形分割による内外判定 $O(\log N)$

ヒント

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

def inside_convex(poly, q):
    n = len(poly)
    p0 = poly[0]
    c1 = cross2d(p0, poly[1], q)
    cn = cross2d(p0, poly[-1], q)
    if c1 < 0 or cn > 0:
        return False
    lo, hi = 1, n-1
    while lo+1 < hi:
        mid = (lo+hi)//2
        if cross2d(p0, poly[mid], q) >= 0:
            lo = mid
        else:
            hi = mid
    return cross2d(poly[lo], poly[lo+1 if lo+1 < n else 0], q) >= 0

模範解答

import sys, math
input = sys.stdin.readline

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

def seg_dist(p, a, b):
    ax, ay = a; bx, by = b; px, py = p
    abx, aby = bx-ax, by-ay
    apx, apy = px-ax, py-ay
    ab2 = abx*abx + aby*aby
    if ab2 == 0:
        return math.hypot(apx, apy)
    t = max(0.0, min(1.0, (apx*abx + apy*aby) / ab2))
    return math.hypot(px - (ax + t*abx), py - (ay + t*aby))

def inside_convex(poly, q):
    n = len(poly)
    p0 = poly[0]
    c1 = cross2d(p0, poly[1], q)
    cn = cross2d(p0, poly[-1], q)
    if c1 < 0 or cn > 0:
        return False
    lo, hi = 1, n-1
    while lo+1 < hi:
        mid = (lo+hi)//2
        if cross2d(p0, poly[mid], q) >= 0:
            lo = mid
        else:
            hi = mid
    nxt = lo+1 if lo+1 < n else 0
    return cross2d(poly[lo], poly[nxt], q) >= 0

def min_dist_to_convex(poly, q):
    n = len(poly)
    if inside_convex(poly, q):
        return 0.0
    best = float('inf')
    for i in range(n):
        d = seg_dist(q, poly[i], poly[(i+1)%n])
        if d < best:
            best = d
    return best

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N, Q = int(data[idx]), int(data[idx+1]); idx += 2
    poly = []
    for _ in range(N):
        x, y = int(data[idx]), int(data[idx+1]); idx += 2
        poly.append((x, y))
    results = []
    for _ in range(Q):
        qx, qy = int(data[idx]), int(data[idx+1]); idx += 2
        d = min_dist_to_convex(poly, (qx, qy))
        if d == 0.0:
            results.append("INSIDE 0.000000")
        else:
            results.append(f"OUTSIDE {d:.6f}")
    print('\n'.join(results))

solve()

Step-by-Step 解説

Step 1: 外積による位置関係

外積 $(A-O) \times (B-O)$ の符号: 正→$B$ は $OA$ の左（反時計方向）、負→右（時計方向）、0→共線。

Step 2: 凸多角形の内外判定 $O(\log N)$

凸多角形を頂点 $P_0$ から「扇形」に分割。クエリ点 $q$ が:

1. 扇形の角度範囲内か: $P_0P_1$ より反時計側かつ $P_0P_{N-1}$ より時計側
2. 二分探索でどのセクター（三角形 $P_0P_iP_{i+1}$）に属するか特定
3. 対応する辺 $P_iP_{i+1}$ の左側にあるかチェック

Step 3: 最近点距離の計算

点 $p$ と線分 $ab$ の最近点: $t = \text{clamp}(\frac{\vec{ap} \cdot \vec{ab}}{|\vec{ab}|^2}, 0, 1)$ として $\text{最近点} = a + t \cdot \vec{ab}$。全 $N$ 辺の最小値を取る。

よくあるミス

次のステップ

• 発展: 凸多角形と凸多角形の距離計算（回転キャリパー法 $O(N+M)$）
• 発展: 動的凸包（Li Chao Tree による双対変換）
• 発展: 凸多角形のミンコフスキー和

自己評価