Day 129-Q5 | Convex Layers（凸包の層構造・Onion Peeling）

問題

平面上に$N$個の点（一般位置）が与えられる。残っている点の凸包を層として割り当てて取り除く操作を、点がなくなるまで繰り返す。各点（入力順）の層番号を出力せよ。

入力形式

N
x_1 y_1
...
x_N y_N

制約

$1 \le N \le 2000$

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

一般位置（3点以上の共線・同一座標なし）

入出力例

入力例1

出力例1

1 1 1 1 2 2 2 2 3

外側の正方形4点が層1、内側の正方形4点が層2、中心の点が層3。

概念図

ヒント（段階的開示）

ヒント1（方向性）

$N \le 2000$程度なら凸包を求めて取り除くのを単純に繰り返すだけで十分（各回O(N log N)、最大O(N)回で合計O(N^2 log N)）。Andrew's Monotone Chainが正しく実装できることが前提。

ヒント2（アプローチ）

残り点集合が2点以下になったときは凸包の概念が退化する（線分や単一点）ため、通常の凸包アルゴリズムをそのまま適用せず「残っている点全部がその層」という特別扱いをする。

ヒント3（誘導）

def convex_hull(points):
    pts = sorted(points)
    if len(pts) <= 2:
        return pts[:]
    def cross(o, a, b):
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
    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]

これを「凸包上の点を取り除いては残りに再適用」というループで包む。

模範解答 (Python)

import sys


def convex_hull(points):
    pts = sorted(points)
    if len(pts) <= 2:
        return pts[:]

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

    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 solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    pts = []
    for i in range(n):
        x = int(data[idx]); idx += 1
        y = int(data[idx]); idx += 1
        pts.append((x, y, i))

    layer = [0] * n
    remaining = pts[:]
    cur_layer = 0

    while remaining:
        cur_layer += 1
        coords = [(p[0], p[1]) for p in remaining]
        hull_set = set(convex_hull(coords))
        new_remaining = []
        for p in remaining:
            if (p[0], p[1]) in hull_set:
                layer[p[2]] = cur_layer
            else:
                new_remaining.append(p)
        remaining = new_remaining

    print(' '.join(map(str, layer)))


solve()

Step-by-Step 解説

1元インデックスの保持
各点に(x,y,i)で元の入力インデックスを付与し、最後に元の順番で出力できるようにする。

2凸包上の点の判定
convex_hullの返す点集合をsetにし、残り点がその集合に含まれるかで今回の層に属するか判定する。

3層の割り当てと除去
凸包に含まれる点に現在の層番号を割り当て、残りだけを次のループへ持ち越す。空になるまで繰り返す。

4退化ケースの処理
len(pts) <= 2のとき1点なら単一点、2点なら両端点をそのまま返す。

5計算量
最悪ケース(同心円状配置)で層数O(N)、全体O(N^2 log N)。Chanのアルゴリズムを応用したO(N log^2 N)解法も知られる。

よくあるミス

ミス	原因	正しい書き方
<=0ではなく<0を使い共線点を残す	monotone chainのpop条件の理解不足	一般位置なら<=0で問題ないが共線点を許す問題では別途対処
残り点1〜2点で通常のループを回しエラーになる	退化ケースの考慮漏れ	関数冒頭で`len(pts) <= 2`を特別扱いする
座標一致判定にfloatを混ぜて誤判定	浮動小数点誤差	整数座標のまま扱いfloat変換を避ける
層番号割り当てが1つずれる	取り除いた後に割り当てる誤った順序	凸包を求めたその回の間に層番号を確定させる

次のステップ

発展: Chanのアルゴリズムのアイデアを応用したO(N log^2 N) Convex Layers、または点が動的に追加される場合のオンライン層更新
次回予告: 未定（次回セッションで新しいテーマ5つを選定）

自己評価

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

Day 129-Q5 — Convex Layers（凸包の層構造・Onion Peeling）

問題