Day 021-Q5 | 凸多角形の最遠点対・回転キャリパー法

問題

$N$ 点の点集合 $P = \{p_1, p_2, \ldots, p_N\}$ が与えられる。

凸包を求めよ
凸包上の最遠点対（Diameter）の距離の 2 乗を求めよ
凸包上の任意の点（整数または有理数座標）で実現される最遠点対を 1 組出力せよ

さらに、凸包の幅（Width = 最小外接帯幅）も求めよ。

入力形式

N
x_1 y_1
x_2 y_2
...
x_N y_N

制約

$3 \leq N \leq 10^5$

$-10^9 \leq x_i, y_i \leq 10^9$

整数座標

3点以上が凸包上に乗る（一般位置保証なし）

入出力例

入力例 1

出力例 1

34
0 0
4 3
Width: ...

ヒント (段階的開示)

ヒント1: 方向性

回転キャリパー法（Rotating Calipers）: 凸包の対蹠点対を $O(N)$ で列挙するアルゴリズム。2本の「キャリパー」（平行支持線）を凸包に当てて反時計回りに回転させる。

ヒント2: アプローチ

(1) 凸包を反時計回りに構築（Graham scan / Andrew's monotone chain）、(2) 最初のキャリパー: 最も下の点と最も上の点にセット、(3) 一方のキャリパーを次の辺まで回転させ、都度距離を計算、(4) 一周したら完了。

ヒント3: 誘導

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(points):
    points = sorted(set(points))
    n = len(points)
    if n <= 1: return points
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

模範解答 (Python)

import sys
from math import gcd

def solve():
    data = sys.stdin.read().split()
    pos = 0
    N = int(data[pos]); pos += 1
    points = []
    for _ in range(N):
        x = int(data[pos]); pos += 1
        y = int(data[pos]); pos += 1
        points.append((x, y))

    def cross(O, A, B):
        return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0])

    def dist2(A, B):
        return (A[0]-B[0])**2 + (A[1]-B[1])**2

    # Andrew's Monotone Chain 凸包
    pts = sorted(set(points))
    n = len(pts)
    if n == 1:
        print(0)
        print(pts[0][0], pts[0][1])
        print(pts[0][0], pts[0][1])
        return

    lower = []
    for p in pts:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(pts):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    hull = lower[:-1] + upper[:-1]
    h = len(hull)

    if h == 1:
        print(0)
        print(hull[0][0], hull[0][1])
        print(hull[0][0], hull[0][1])
        return
    if h == 2:
        d2 = dist2(hull[0], hull[1])
        print(d2)
        print(hull[0][0], hull[0][1])
        print(hull[1][0], hull[1][1])
        return

    # 回転キャリパー法でDiameter
    max_d2 = 0
    best_pair = (hull[0], hull[1])
    j = 0
    for i in range(h):
        while True:
            nj = (j + 1) % h
            A = hull[i]
            B = hull[(i+1) % h]
            c_cur = cross(A, B, hull[j])
            c_nxt = cross(A, B, hull[nj])
            if c_nxt > c_cur:
                j = nj
            else:
                break

        for di in [hull[i], hull[(i+1)%h]]:
            d = dist2(di, hull[j])
            if d > max_d2:
                max_d2 = d
                best_pair = (di, hull[j])

    print(max_d2)
    print(best_pair[0][0], best_pair[0][1])
    print(best_pair[1][0], best_pair[1][1])

    # 幅（Width）: 最小外接帯
    min_width_num = float('inf')
    min_width_den = 1

    j = 0
    for i in range(h):
        A = hull[i]
        B = hull[(i+1) % h]
        edge_len2 = dist2(A, B)
        if edge_len2 == 0:
            continue

        while True:
            nj = (j + 1) % h
            c_cur = cross(A, B, hull[j])
            c_nxt = cross(A, B, hull[nj])
            if c_nxt > c_cur:
                j = nj
            else:
                break

        c = cross(A, B, hull[j])  # = |AB| * height
        if c * c * min_width_den < min_width_num * edge_len2:
            min_width_num = c * c
            min_width_den = edge_len2

    g = gcd(min_width_num, min_width_den)
    print(f"Width^2 = {min_width_num//g}/{min_width_den//g}")

solve()

Step-by-Step 解説

1凸包構築（Andrew's Monotone Chain）
点をx座標（同じならy座標）でソートし、下側凸包と上側凸包を別々に構築。外積が $\leq 0$ の点をスタックから除く（左折りしない）。計算量: $O(N \log N)$。

2回転キャリパー法のアイデア
凸包上の対蹠点対は「回転する平行線（キャリパー）」で捉えられる。辺 $(hull[i], hull[i+1])$ を一方のキャリパーに固定し、もう一方のキャリパーが当たる最遠点 $hull[j]$ を管理。辺を一つ進めるごとに $j$ も単調に進む → 全体 $O(N)$。

3幅（Width）の計算
各辺に対する「反対側の最遠点からの距離」が外接帯幅の候補。外積 $= |辺| \times 高さ$ を利用して整数演算のまま比較。

4整数演算の精度
浮動小数点を使わず、距離の 2 乗や外積（整数）で比較することで精度を保つ。

よくあるミス

ミス	原因	正しい書き方
凸包を時計回りで構築	cross <= 0 の条件が逆	反時計回り: `cross <= 0` でpop
キャリパーの進め方を誤る	距離ではなく外積で進める	`cross(A, B, hull[nj]) > cross(A, B, hull[j])`
重複点でdivide by zero	edge_len2 が 0	`if edge_len2 == 0: continue`

Day 021-Q5 — 凸多角形の最遠点対・回転キャリパー法

問題