Day 051-Q2 | Randomized Incremental Convex Hull（動的凸包・内部判定クエリ）

問題

2次元平面上に $N$ 点が与えられる。次の $Q$ 個のクエリを処理せよ。

クエリ型 1: 1 x y — 点 $(x, y)$ を追加する
クエリ型 2: 2 x y — 点 $(x, y)$ が現在の点集合の凸包の内部または境界にあるかを判定し YES か NO を出力

制約

パラメータ	範囲
$N, Q$	$1 \le N, Q \le 10^5$
座標	$\|x\|, \|y\| \le 10^9$（整数）
時間制限	3秒

入出力例

入力例 1

出力例 1

YES
NO

初期点集合は正方形 [0,4]×[0,4]。(3,3) は内部 → YES。(5,5) は外部 → NO。

概念図: 上凸包・下凸包の分離管理

ヒント（段階的開示）

ヒント1: 方向性

動的凸包を「上凸包」と「下凸包」に分けて SortedList（平衡 BST）で管理。点追加時は不要な頂点を削除し、内部判定は上下の包絡線と比較する。

ヒント2: アプローチ

上凸包: x 座標順で右折（cross ≤ 0）のみの折れ線
下凸包: 左折（cross ≥ 0）のみの折れ線
点 $(x, y)$ の内部判定: x が凸包の x 範囲内、かつ $lower\_y(x) \le y \le upper\_y(x)$
浮動小数点を避け、$y \le y_1 + (y_2-y_1)(x-x_1)/(x_2-x_1)$ を整数の分子・分母で比較

ヒント3: 実装骨格

from sortedcontainers import SortedList

def cross(O, A, B):
    return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0])

class DynamicConvexHull:
    def __init__(self):
        self.upper = {}  # x -> y
        self.lower = {}
        self.ux = SortedList()
        self.lx = SortedList()

    def add(self, x, y):
        # 上凸包に (x, y) を追加して不要点を削除
        self.upper[x] = max(self.upper.get(x, -inf), y)
        self.ux.add(x)
        self._rebuild_upper()
        # 下凸包も同様
        ...

    def contains(self, x, y):
        # upper_y(x) と lower_y(x) を線形補間で計算し比較
        ...

模範解答 (Python)

import sys
from sortedcontainers import SortedList
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])

class DynamicConvexHull:
    def __init__(self):
        self.upper = {}; self.lower = {}
        self.ux = SortedList(); self.lx = SortedList()

    def _rebuild_upper(self):
        pts = [(x, self.upper[x]) for x in self.ux]
        hull = []
        for p in pts:
            while len(hull)>=2 and cross(hull[-2],hull[-1],p)>=0:
                hull.pop()
            hull.append(p)
        self.upper = {p[0]:p[1] for p in hull}
        self.ux = SortedList(self.upper.keys())

    def _rebuild_lower(self):
        pts = [(x, self.lower[x]) for x in self.lx]
        hull = []
        for p in pts:
            while len(hull)>=2 and cross(hull[-2],hull[-1],p)<=0:
                hull.pop()
            hull.append(p)
        self.lower = {p[0]:p[1] for p in hull}
        self.lx = SortedList(self.lower.keys())

    def add(self, x, y):
        if x not in self.upper or self.upper[x] < y:
            self.upper[x] = y
            if x not in self.ux: self.ux.add(x)
            self._rebuild_upper()
        if x not in self.lower or self.lower[x] > y:
            self.lower[x] = y
            if x not in self.lx: self.lx.add(x)
            self._rebuild_lower()

    def _interp_upper(self, x):
        if not self.ux or x < self.ux[0] or x > self.ux[-1]: return None
        if x in self.upper: return (self.upper[x], 1)
        idx = self.ux.bisect_right(x)
        if idx==0 or idx>=len(self.ux): return None
        x1,x2 = self.ux[idx-1],self.ux[idx]
        y1,y2 = self.upper[x1],self.upper[x2]
        return (y1*(x2-x1)+(y2-y1)*(x-x1), x2-x1)

    def _interp_lower(self, x):
        if not self.lx or x < self.lx[0] or x > self.lx[-1]: return None
        if x in self.lower: return (self.lower[x], 1)
        idx = self.lx.bisect_right(x)
        if idx==0 or idx>=len(self.lx): return None
        x1,x2 = self.lx[idx-1],self.lx[idx]
        y1,y2 = self.lower[x1],self.lower[x2]
        return (y1*(x2-x1)+(y2-y1)*(x-x1), x2-x1)

    def contains(self, x, y):
        u = self._interp_upper(x); l = self._interp_lower(x)
        if u is None or l is None: return False
        un,ud = u; ln,ld = l
        return y*ud <= un and y*ld >= ln

def solve():
    N, Q = map(int, input().split())
    dch = DynamicConvexHull()
    for _ in range(N):
        x,y = map(int, input().split()); dch.add(x,y)
    out = []
    for _ in range(Q):
        line = list(map(int, input().split()))
        if line[0]==1: dch.add(line[1],line[2])
        else: out.append('YES' if dch.contains(line[1],line[2]) else 'NO')
    print('\n'.join(out))

solve()

Step-by-Step 解説

1上凸包・下凸包の分離
凸包を上下に分けると、x 座標でソートされた単調な折れ線として管理できる。SortedList で $O(\log N)$ の挿入・削除。

2外積による折れ曲がり判定
$\text{cross}(O, A, B) = (A-O) \times (B-O)$。上凸包は常に右折（cross < 0）が必要。中間点 A が不要なとき（cross ≥ 0）は削除。

3点の追加と凸包再構築
新点追加後 Graham scan で不要な中間点を削除して凸包を維持。

4内部判定（整数演算）
点 $(x, y)$ の x の前後の凸包点を線形補間：$y_{\text{upper}}(x) = y_1 + (y_2-y_1)(x-x_1)/(x_2-x_1)$。
浮動小数点を避け $(y_1(x_2-x_1) + (y_2-y_1)(x-x_1))$ vs $y \cdot (x_2-x_1)$ を整数比較。

計算量

点追加: 償却 $O(\log N)$（Graham scan で削除される点は再追加されない）
内部判定: $O(\log N)$（SortedList の二分探索）
全体: $O((N + Q) \log N)$
空間: $O(N)$

よくあるミス

ミス	原因	正しい書き方
上下凸包でクロス積の符号を混同	上は右折(cross<0)、下は左折(cross>0)	コメントで明示し、テストケースで確認
浮動小数点で補間	精度誤差で判定ミス	整数の分子・分母で比較
x が端点のときの特殊処理漏れ	補間で idx-1 が無効	bisect で端点チェックしてから補間
同一 x で複数点	上凸包の y は最大、下は最小	`upper[x] = max(upper.get(x,-inf), y)`

次のステップ

発展問題: 動的凸包での最遠点クエリ（Li Chao Tree との関係）
関連: Kinetic Heap と凸包の融合（動的最小値追跡）
応用: オンライン 3D 凸包（Quickhull のオンライン版）

自己評価

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