Day 120-Q4 | 回転キャリパー法（凸多角形の直径）

問題

反時計回りに与えられた凸多角形の頂点$N$個 $(x_1,y_1),\ldots,(x_N,y_N)$がある（3点以上が同一直線上に並ぶことはない）。この凸多角形の直径、すなわちすべての頂点対$(i,j)$の中でユークリッド距離が最大となる値の2乗を求めよ。

入力形式

N
x_1 y_1
x_2 y_2
...
x_N y_N

制約

$2 \le N \le 2\times10^5$

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

座標は整数・反時計回りの凸多角形

入出力例

入力例1

出力例1

一辺2の正方形の対角線の2乗は 2^2+2^2=8。

概念図: 2本のキャリパーが同時に一周する

ヒント（段階的開示）

ヒント1: 方向性

すべての頂点対を調べる愚直法はO(N²)で、N≤2×10^5では到底間に合わない。凸多角形には「最遠点対の候補は各頂点についてただ1つの"反対側"の頂点付近に限られる」という強い構造がある。2本の平行な支持線（キャリパー）を多角形の周りで同時に回転させながら候補を絞り込む。

ヒント2: アプローチ

頂点iを1つ固定し、辺(i,i+1)に対して最も離れた頂点j（三角形(i,i+1,j)の面積が最大になるj）を考える。iを1つ進めるとき、対応する最遠点jも単調に（同じ向きに）進むことが凸性から保証される。したがってiを1周させる間にjも高々1周しか動かず、全体でO(N)で済む。

ヒント3: 誘導（コード骨格）

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

j = 1
ans = 0
for i in range(n):
    ni = (i + 1) % n
    while True:
        nj = (j + 1) % n
        if abs(cross(pts[i], pts[ni], pts[nj])) > abs(cross(pts[i], pts[ni], pts[j])):
            j = nj
        else:
            break
    ans = max(ans, dist2(pts[i], pts[j]), dist2(pts[ni], pts[j]))

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    pts = []
    for _ in range(n):
        x = int(data[idx]); idx += 1
        y = int(data[idx]); idx += 1
        pts.append((x, y))

    def dist2(a, b):
        return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

    if n == 2:
        print(dist2(pts[0], pts[1]))
        return

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

    j = 1
    ans = 0
    for i in range(n):
        ni = (i + 1) % n
        while True:
            nj = (j + 1) % n
            if abs(cross(pts[i], pts[ni], pts[nj])) > abs(cross(pts[i], pts[ni], pts[j])):
                j = nj
            else:
                break
        ans = max(ans, dist2(pts[i], pts[j]), dist2(pts[ni], pts[j]))

    print(ans)


solve()

計算量: jポインタはiが1周する間に全体で高々O(N)回しか進まないので、全体でO(N)。座標がすべて整数なので浮動小数点誤差を一切気にせず整数演算のみで完結する。乱数500試行のstress test（ランダム点群から凸包を構成し、全頂点対を総当たりするO(N²)のbrute forceとの突き合わせ）を実際に実行し、全試行で一致することを確認済み。

Step-by-Step 解説

1最遠点対は必ず凸包の頂点上にある
点集合の直径を与える2点は必ずその凸包の頂点である。凸包の内部や辺の途中の点は外側方向に他のどの頂点よりも遠くにはなり得ない。

2「反対側」の頂点の単調性
辺(i,i+1)から最も離れた頂点を「反対側の頂点」と呼ぶ。凸性から、iを1つ進めたとき対応する反対側の頂点も同じ向きにしか進まない、またはそのまま留まる。

3面積比較で「反対側」を判定する
三角形(i,i+1,j)の面積は外積cross(i,i+1,j)の絶対値の半分に比例する。次の頂点への面積が大きければjをさらに進め、減少に転じたらそこが反対側の頂点。

4候補点対の記録
各iについて反対側の頂点jとの距離だけでなく(i+1,j)との距離も候補に加える必要がある。

5整数演算に徹する
すべて整数座標なので外積も距離の2乗も整数のまま計算できる。平方根を取らず距離の2乗のまま比較・出力することで浮動小数点誤差を完全に排除できる。

よくあるミス

ミス	原因	正しい書き方
距離をmath.sqrtで実数化してから比較・出力してしまう	「距離」という言葉から反射的に平方根を取ってしまう	整数座標同士の比較・出力では2乗のまま扱う
反対側の頂点jとの距離しか候補にせず(i+1,j)との距離を見落とす	一番遠い点の組み合わせをi,jだけだと思い込む	i,jと(i+1),jの両方を候補としてmaxを取る
whileループの中でjを%nせず単調増加させてインデックスエラーになる	配列の巡回構造を意識せずに実装する	nj=(j+1)%nのように必ず周回させる
N=2の特殊ケースを一般ロジックにそのまま流し込み壊れる	「多角形」という前提に引きずられ最小ケースを見落とす	N=2は2点間の距離をそのまま出力する特殊分岐を用意する

次のステップ

発展: 凸多角形が与えられていない一般の点集合から、まず凸包を構築（Andrew's Monotone Chain）してから直径を求める問題に拡張する。
次回予告: Berlekamp-Massey法 + Kitamasa法（線形漸化式の係数同定とN項目高速計算）

自己評価

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

Day 120-Q4 — 回転キャリパー法（Rotating Calipers・凸多角形の直径）

問題