Day 111-Q5 | 回転キャリパー法（最小外接矩形）

問題

平面上に $N$ 個の点が与えられる。全ての点を内部または境界上に含む長方形（任意の向きに回転してよい）のうち、面積が最小のものの面積を求めよ。

入力形式

N
x_1 y_1
...
x_N y_N

制約

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

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

全点が同一直線上にあることはない

入出力例

入力例1

出力例1

10.000000

軸平行の外接矩形面積は$4\times4=16$だが、辺に沿って傾けると面積$10$まで小さくできる。

概念図: 凸包の辺に沿った回転キャリパー

ヒント（段階的開示）

ヒント1: 方向性

全ての回転角を試す発想は正しいが角度は連続量。最適な矩形が特定の角度で実現されるという強い性質を利用したい。

ヒント2: アプローチ

(1)凸包の頂点だけを考えれば十分。(2)最小外接矩形は必ず凸包のいずれかの辺と1辺を共有する（回転キャリパーの定理）。各辺の方向$\vec d$と法線$\vec n$に全頂点を内積で射影し、幅・高さの積を$|\vec d|^2$で割って面積を求め、全辺の最小値を取る。

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

for i in range(H):
    p1, p2 = hull[i], hull[(i+1)%H]
    dx, dy = p2[0]-p1[0], p2[1]-p1[1]
    L2 = dx*dx + dy*dy
    us = [(q[0]-p1[0])*dx + (q[1]-p1[1])*dy for q in hull]
    vs = [(q[0]-p1[0])*(-dy) + (q[1]-p1[1])*dx for q in hull]
    area = (max(us)-min(us)) * (max(vs)-min(vs)) / L2
    best = min(best, area)

模範解答 (Python)

import sys

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):
    pts = sorted(set(points))
    if len(pts) <= 2:
        return pts
    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)
    return lower[:-1] + upper[:-1]

def min_rect_area(points):
    hull = convex_hull(points)
    h = len(hull)
    if h <= 2:
        return 0.0
    best = float('inf')
    for i in range(h):
        p1 = hull[i]
        p2 = hull[(i + 1) % h]
        dx, dy = p2[0] - p1[0], p2[1] - p1[1]
        l2 = dx * dx + dy * dy
        if l2 == 0:
            continue
        us, vs = [], []
        for q in hull:
            qx, qy = q[0] - p1[0], q[1] - p1[1]
            us.append(qx * dx + qy * dy)
            vs.append(qx * (-dy) + qy * dx)
        width_raw = max(us) - min(us)
        height_raw = max(vs) - min(vs)
        area = (width_raw * height_raw) / l2
        if area < best:
            best = area
    return best

def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    points = []
    for _ in range(n):
        x = int(data[idx]); y = int(data[idx + 1]); idx += 2
        points.append((x, y))
    ans = min_rect_area(points)
    print(f"{ans:.6f}")

solve()

計算量: 凸包構築$O(N\log N)$、各辺の射影が$O(H)$なので全辺で$O(H^2)$（真の回転キャリパーなら$O(H)$）。200ケースのランダム凸多角形で角度$2\times10^4$分割の粗い基準実装と比較し、常に基準実装以下（離散化誤差範囲で一致）であることを確認済み。入力例1で厳密に面積$10.0$が得られることも確認済み。

Step-by-Step 解説

1凸包だけを考えればよい理由
凸包の外側にはみ出さない矩形は凸包内部の点も自動的に含む。

2最小矩形が凸包の辺と1辺を共有する理由
どの辺とも接していない矩形は、わずかに回転させることで面積をさらに小さくできてしまう。

3ある辺を軸にした面積の計算
辺ベクトル$\vec d$と法線$\vec n$への射影の最大・最小差を「幅」「高さ」とし、$|\vec d|^2$で割って面積を得る。

4全辺を試して最小値を取る
凸包の$H$個の辺それぞれについてStep3を行い最小値を答えとする。

5さらなる高速化
支持点が単調にしか進まない性質を使い4本のキャリパーを2ポインタで管理すれば$O(H)$に落とせる。

よくあるミス

ミス	原因	正しい書き方
軸平行の外接矩形だけを答えにしてしまう	「回転してよい」条件の見落とし	凸包の各辺方向を軸とした矩形を全て試す
法線と辺ベクトルの長さの関係を見落とし面積計算が非効率/不整合になる	$\|\vec n\|^2=\|\vec d\|^2$であることに気づかない	割り算は$dx^2+dy^2$一回だけで済ませる
共線点により辺ベクトルが$(0,0)$になり0除算	凸包構築で厳密な凸性を確認していない	共線点を除去するか$dx=dy=0$のケースをスキップする
出力を整数に丸めてしまう	面積が非整数値になりうることの見落とし	小数点以下6桁程度で浮動小数点出力する

次のステップ

発展: 真の回転キャリパー法（4本のキャリパーの2ポインタ同時進行）で$O(H)$に高速化する
発展: 最小外接円（Day094 Welzl's Algorithm）など関連する幾何最適化問題と比較する
発展: 3次元凸包（Day014）に対する最小体積外接直方体への一般化を調べる

自己評価

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

Day 111-Q5 — 回転キャリパー法による最小外接矩形（Rotating Calipers Minimum Bounding Rectangle）

問題