Day 056-Q1 — Convex Hull + Rotating Calipers 最大三角形面積

問題

$N$ 個の点 $P_1, \ldots, P_N$（整数座標）が与えられる。$Q$ 個の更新クエリに答えながら、常に全点から3点を選んで作られる三角形の面積の最大値の2倍（整数）を出力せよ。

• クエリ A: 現時点の全点で最大三角形面積×2を出力
• クエリ U i x y: 点 $P_i$ を $(x, y)$ に更新

入出力例

5 3
0 0
4 0
4 4
0 4
2 6
A
U 5 2 -2
A

32
16

初期5点の凸包で最大三角形は頂点 $(0,0),(4,0),(2,6)$ など → 面積×2 = 32。
$P_5$ を $(2,-2)$ に更新後 → 最大三角形面積×2 = 16。

概念図: 凸包と回転キャリパー

ヒント（段階的開示）

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

def max_triangle_area2(hull):
    h = len(hull)
    ans = 0
    for i in range(h - 1):
        k = i + 2
        for j in range(i + 1, h):
            while cross(hull[i], hull[j], hull[(k+1)%h]) > \
                  cross(hull[i], hull[j], hull[k%h]):
                k += 1
            ans = max(ans, cross(hull[i], hull[j], hull[k%h]))
    return ans

模範解答 (Python)

コピーimport sys
input = sys.stdin.readline

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(pts):
    pts = sorted(set(pts))
    n = len(pts)
    if n <= 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 max_triangle_area2(hull):
    h = len(hull)
    if h < 3:
        return 0
    ans = 0
    for i in range(h - 1):
        k = i + 2
        for j in range(i + 1, h):
            nk = (k + 1) % h
            while cross(hull[i], hull[j], hull[nk]) > cross(hull[i], hull[j], hull[k % h]):
                k += 1
                nk = (k + 1) % h
            c = cross(hull[i], hull[j], hull[k % h])
            if c > ans:
                ans = c
    return ans

def solve():
    N, Q = map(int, input().split())
    pts = []
    for _ in range(N):
        x, y = map(int, input().split())
        pts.append((x, y))

    out = []
    for _ in range(Q):
        line = input().split()
        if line[0] == 'A':
            hull = convex_hull(pts)
            out.append(str(max_triangle_area2(hull)))
        else:
            i, x, y = int(line[1])-1, int(line[2]), int(line[3])
            pts[i] = (x, y)

    print('\n'.join(out))

solve()

Step-by-Step 解説

Step 1: Andrew's Monotone Chain

座標でソートし、下側凸包・上側凸包を順に構築する。外積が非正なら後退（共線点を除外）。計算量 $O(N \log N)$。

Step 2: 最大三角形の性質

最大面積三角形の3頂点は必ず凸多角形の頂点。内部点を加えても面積は改善しない（三角形面積の単調性）。

Step 3: 回転キャリパー

辺 $(i, j)$ を固定したとき、最遠点 $k$ は $j$ を増やすにつれて単調に進む。$k$ のポインタをリセットしないため、固定 $i$ に対する全 $j$ の走査で $k$ の総進み量は $O(H)$。全体 $O(H^2)$。

計算量

よくあるミス

次のステップ

• 発展: 最大内接三角形（円周上の点での面積最大化）
• 関連問題: AtCoder ABC 151 D, ABC 166 E（凸包応用）
• 最遠点対（直径）: 回転キャリパーで $O(H)$

自己評価