Day 085-Q4 — 凸層分解（Convex Layers / Onion Peeling・$O(N^2 \log N)$）

問題

平面上に $N$ 個の点が与えられる。次の操作を繰り返す。

1. 現在残っている点の凸包（境界上の点）を1つの「層」として取り出し、除去する。
2. 点がなくなるまで繰り返す。

各点が何番目の層（最外層を層1）に属するかを求め、各層の頂点数を層番号順に出力せよ。

入出力例

7
0 0
4 0
4 4
0 4
2 2
1 1
3 3

1 1 1 1 3 2 2
4 2 1

外周4点が層1、$(1,1),(3,3)$ が層2、$(2,2)$ が層3。

概念図: 玉ねぎのように凸包を剥がす

ヒント

remaining = list(range(N)); L = 0
while remaining:
    L += 1
    hull = convex_hull([i for i in remaining])  # インデックス付き
    hset = set(hull)
    for i in hset: layer[i] = L
    remaining = [i for i in remaining if i not in hset]

模範解答

import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    P = [tuple(map(int, input().split())) for _ in range(N)]

    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(idx):
        pts = sorted(idx, key=lambda i: (P[i][0], P[i][1]))
        if len(pts) <= 2:
            return list(pts)
        def half(seq):
            h = []
            for i in seq:
                while len(h) >= 2 and cross(P[h[-2]], P[h[-1]], P[i]) < 0:
                    h.pop()
                h.append(i)
            return h
        lower = half(pts)
        upper = half(pts[::-1])
        return lower[:-1] + upper[:-1]

    layer = [0]*N; sizes = []
    remaining = list(range(N)); L = 0
    while remaining:
        L += 1
        hull = convex_hull(remaining)
        hset = set(hull)
        for i in hset: layer[i] = L
        sizes.append(len(hset))
        remaining = [i for i in remaining if i not in hset]

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

solve()

計算量: 各層 $O(k \log k)$、最大 $O(N)$ 段、合計 $O(N^2 \log N)$。

Step-by-Step 解説

Step 1: 凸包（Andrew's Monotone Chain）

点を $(x,y)$ ソートし、下側・上側の包絡線をスタックで構築。cross < 0 で右折を pop すれば反時計回り凸包。共線点を層に含めるかは < 0（含める）/ <= 0（頂点のみ）で切替。

Step 2: 層番号付与と除去

凸包に載った点集合に現在の層番号を付け、残点集合から除く。set 差分で $O(N)$。

Step 3: 反復回数

Step 4: 出力

layer[i] に各点の層、sizes に層順サイズを蓄積して出力。

よくあるミス

次のステップ

• 発展問題: Chazelle の $O(N \log N)$ Onion Peeling（全層一括構築）
• 発展問題: 凸層を用いた k-th 深さ点クエリ・レベル集合統計

自己評価