Day 159-Q5 — 2026-09-24 — Chan のアルゴリズム（出力依存 $O(n\log h)$ 凸包・Graham と Jarvis を「サイズを当てながら」合体する）

📋 コピー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 monotone_chain(pts):
    """Andrew の単調鎖。CCW、共線点は除く。O(k log k)"""
    pts = sorted(pts)
    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 better(p, a, b):
    """p から見て a を b より優先するか（Jarvis の次頂点として）。共線なら遠い方。"""
    c = cross(p, b, a)
    if c != 0:
        return c < 0
    return (a[0]-p[0])**2 + (a[1]-p[1])**2 > (b[0]-p[0])**2 + (b[1]-p[1])**2


def tangent_index(hull, p):
    """CCW 凸多角形 hull と外部点 p に対し「全頂点が有向直線 p->hull[i] の左側（または直線上）」
    となる接点 i を O(log n) で返す。Sunday (geomalgorithms.com, tangent_PointPoly) の二分探索。
    p が辺の延長線上にある退化では 1〜2 個ずれるので、隣へ登れる限り登る（退化時のみ数歩）。"""
    n = len(hull)
    if n == 1:
        return 0
    if n == 2:
        return 0 if better(p, hull[0], hull[1]) else 1

    def above(a, b): return cross(p, a, b) > 0      # b は有向直線 p->a の左
    def below(a, b): return cross(p, a, b) < 0

    def between(a, b):                              # p が線分 ab 上（共線前提）
        return (min(a[0], b[0]) <= p[0] <= max(a[0], b[0]) and
                min(a[1], b[1]) <= p[1] <= max(a[1], b[1]))

    def prefer(j, i):                               # 頂点 i の代わりに j を採るべきか
        c = cross(p, hull[i], hull[j])
        if c != 0:
            return c < 0
        if between(hull[i], hull[j]):               # p が辺の内部 → CCW で次の端点
            return j == (i + 1) % n
        return better(p, hull[j], hull[i])          # 延長線上 → 遠い方

    def fix(i):
        while True:
            for j in ((i + 1) % n, (i - 1) % n):
                if prefer(j, i):
                    i = j
                    break
            else:
                return i

    if below(hull[1], hull[0]) and not above(hull[n - 1], hull[0]):
        return fix(0)
    a, b = 0, n
    while b - a > 1:
        c = (a + b) // 2
        dnC = below(hull[(c + 1) % n], hull[c])
        if dnC and not above(hull[c - 1], hull[c]):
            return fix(c)
        upA = above(hull[(a + 1) % n], hull[a])
        if upA:
            if dnC:
                b = c
            elif above(hull[a], hull[c]):
                b = c
            else:
                a = c
        else:
            if not dnC:
                a = c
            elif below(hull[a], hull[c]):
                b = c
            else:
                a = c
    return fix(a)


def chan(pts):
    n = len(pts)
    if n <= 2:
        return sorted(pts)
    start = min(pts)
    t = 1
    while True:
        m = min(n, 1 << (1 << t))                   # m = 2^(2^t): 4, 16, 256, 65536, ...
        hulls = [monotone_chain(pts[i:i + m]) for i in range(0, n, m)]
        pos = [{q: i for i, q in enumerate(h)} for h in hulls]   # cur を含む群では次頂点は隣
        hull = [start]; cur = start
        for _ in range(m):                          # m 歩以内に閉じなければ失敗
            cand = None
            for h, ps in zip(hulls, pos):
                if cur in ps:
                    if len(h) == 1:
                        continue
                    q = h[(ps[cur] + 1) % len(h)]
                else:
                    q = h[tangent_index(h, cur)]
                if cand is None or better(cur, q, cand):
                    cand = q
            if cand == start:
                return hull
            hull.append(cand); cur = cand
        t += 1


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    pts = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)]
    hull = chan(pts)
    out = [str(len(hull))] + [f"{x} {y}" for x, y in hull]
    sys.stdout.write("\n".join(out) + "\n")


main()