Day 132-Q2 | 分割統治法による凸包構築

問題

2次元平面上に$N$個の点がある。どの3点も一直線上にない（一般の位置にある）ことが保証されている。これらの点の凸包（すべての点を含む最小の凸多角形）を、分割統治法を用いて構築せよ。凸包の頂点数$K$と、凸包の面積の2倍（$2\times\text{Area}$、整数値）を出力せよ。

入力形式

N
x_1 y_1
x_2 y_2
...
x_N y_N

制約

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

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

点はすべて異なり、どの3点も一直線上にない

入出力例

入力例1

出力例1

5 30

この入力では点$(2,1)$のみが凸包内部に含まれ、残り5点すべてが凸包の頂点になる。

概念図

ヒント（段階的開示）

ヒント1（方向性）

凸包を求めるアルゴリズムとしてはAndrewのMonotone Chain（下側+上側包絡線）が有名だが、ここではあえて分割統治法で構築する。点をx座標でソートして左右に分割し、それぞれの凸包を再帰的に求めてから「マージ」する、マージソートと同じ骨格のアルゴリズムである。

ヒント2（アプローチ）

左凸包L（CCW）と右凸包R（CCW）が求まっているとき、上側共通接線（すべての点が線の下側）と下側共通接線（すべての点が線の上側）の2本を見つければマージできる。Lの「上接点から下接点まで（外側の弧）」とRの「下接点から上接点まで（外側の弧）」をつなげば、マージ後の凸包になる。

ヒント3（誘導）

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

def upper_tangent(L, R, i0, j0):
    n1, n2 = len(L), len(R)
    i, j = i0, j0
    while True:
        moved = False
        while cross(L[i], R[j], L[(i + 1) % n1]) > 0:
            i = (i + 1) % n1; moved = True
        while cross(L[i], R[j], R[(j - 1) % n2]) > 0:
            j = (j - 1) % n2; moved = True
        if not moved:
            return i, j

模範解答 (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 small_hull(pts):
    pts = sorted(set(pts))
    if len(pts) <= 2:
        return pts
    c = cross(pts[0], pts[1], pts[2])
    if c > 0:
        return [pts[0], pts[1], pts[2]]
    else:
        return [pts[0], pts[2], pts[1]]

def merge_hulls(L, R):
    n1, n2 = len(L), len(R)
    if n1 == 0:
        return R
    if n2 == 0:
        return L
    i0 = max(range(n1), key=lambda k: (L[k][0], L[k][1]))
    j0 = min(range(n2), key=lambda k: (R[k][0], R[k][1]))

    i, j = i0, j0
    while True:
        moved = False
        while cross(L[i], R[j], L[(i + 1) % n1]) > 0:
            i = (i + 1) % n1
            moved = True
        while cross(L[i], R[j], R[(j - 1) % n2]) > 0:
            j = (j - 1) % n2
            moved = True
        if not moved:
            break
    upper_i, upper_j = i, j

    i, j = i0, j0
    while True:
        moved = False
        while cross(L[i], R[j], L[(i - 1) % n1]) < 0:
            i = (i - 1) % n1
            moved = True
        while cross(L[i], R[j], R[(j + 1) % n2]) < 0:
            j = (j + 1) % n2
            moved = True
        if not moved:
            break
    lower_i, lower_j = i, j

    result = []
    i = upper_i
    result.append(L[i])
    while i != lower_i:
        i = (i + 1) % n1
        result.append(L[i])
    j = lower_j
    result.append(R[j])
    while j != upper_j:
        j = (j + 1) % n2
        result.append(R[j])
    return result

def dc_hull(points):
    pts = sorted(set(points))
    def rec(seq):
        if len(seq) <= 3:
            return small_hull(seq)
        mid = len(seq) // 2
        L = rec(seq[:mid])
        R = rec(seq[mid:])
        return merge_hulls(L, R)
    if len(pts) <= 1:
        return pts
    return rec(pts)

def area2(hull):
    n = len(hull)
    if n < 3:
        return 0
    s = 0
    for i in range(n):
        x1, y1 = hull[i]
        x2, y2 = hull[(i + 1) % n]
        s += x1 * y2 - x2 * y1
    return abs(s)

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

solve()

Step-by-Step 解説

1ソートと分割
点をx（同x座標ならy）でソートし半分に分割。N≤3なら直接凸包を構成する。

2再帰
左右半分をそれぞれ再帰的に解く。マージソートと同じ木構造で深さO(log N)。

3共通接線探索
Lの最右点・Rの最左点から出発し、隣の点がはみ出す間だけポインタを進める。各接線あたりO(|L|+|R|)。

4マージ後の組み立て
Lを上接点から下接点まで（外周の長い方）、続けてRを下接点から上接点までたどればCCW順の頂点列が得られる。

5計算量
T(N)=2T(N/2)+O(N)よりO(N log N)。N≤2×10^5でも再帰深さ約18で十分高速。

よくあるミス

ミス	原因	正しい書き方
共線点があると接線探索が無限ループ・誤判定	cross=0の扱いが曖昧	本問は「一般の位置」を前提にして退化ケースを回避する
接線探索の不等号・回転方向を取り違える	上側と下側で符号・進行方向が逆であることを混同	上側は>0でi:+1,j:-1、下側は<0でi:-1,j:+1、と対で覚える
マージで内側（切り取られる側）の弧を使ってしまう	上接点→下接点の短い方を辿る	上接点から同じ方向へ辿り続け下接点に到達するまで進む
基底ケースで2点を3点扱いしてしまう	small_hullの点数チェック漏れ	len(pts)<=2ならそのまま返す特別扱いを入れる

次のステップ

発展: 共線点を許す頑健な実装（同一直線上の点は両端だけ残すなどの工夫）
発展2: 3次元凸包への一般化（Quickhull・逐次添加法との比較）
次回予告: 次回のテーマは今後のセッションで選定

自己評価

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

Day 132-Q2 — 分割統治法による凸包構築（D&C Convex Hull）

問題