問題
$N$ 点の点群（一般位置: 3点共線なし）が与えられる。以下の2種類のクエリを $Q$ 個処理せよ：
add x y: 点 $(x, y)$ を点群に追加する。query x y: 点 $(x, y)$ が現在の点群の凸包の内部（境界含む）にあるか判定し、YES/NOを出力する。
制約
| パラメータ | 範囲 |
|---|---|
| $N$（初期点数） | $3 \le N \le 10^5$ |
| $Q$（クエリ数） | $1 \le Q \le 10^5$ |
| 座標 | $-10^9 \le x, y \le 10^9$（整数） |
| 条件 | 一般位置（3点共線なし） |
入出力例
入力例 1
4 3
0 0
4 0
4 4
0 4
query 2 2
add 2 5
query 2 4出力例 1
YES
YES概念図: Upper Hull / Lower Hull の動的管理
ヒント（段階的開示）
ヒント1: 方向性
動的凸包（Dynamic Convex Hull）を維持する。Upper Hull と Lower Hull を別々の sorted list で管理し、点追加時に不要な頂点を除去する（Andrew's Monotone Chain の動的版）。
ヒント2: アプローチ
- Upper Hull: $x$ 増加に従い「右折りのみ」（cross product ≤ 0 のとき内点を削除）
- Lower Hull: $x$ 増加に従い「左折りのみ」（cross product ≥ 0 のとき内点を削除）
- 内部判定: $x$ 範囲チェック → 二分探索で前後2点を取得 → 線形補間で $y$ の上下限を計算
ヒント3: コード骨格
def cross(O, A, B):
return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0])
# Upper Hull に点 p を追加
hull = sorted(points)
upper = []
for p in hull:
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) >= 0:
upper.pop()
upper.append(p)
# 内部判定
from bisect import bisect_right
xs = [p[0] for p in upper]
idx = bisect_right(xs, qx) - 1
x1, y1 = upper[idx]; x2, y2 = upper[idx+1]
y_upper = y1 + (y2-y1)*(qx-x1)/(x2-x1)
# lower も同様に取得して lower_y <= qy <= y_upper模範解答 (Python)
import sys
from bisect import bisect_left, bisect_right
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, points):
self.points = sorted(set(points))
self._rebuild()
def _rebuild(self):
pts = self.points
if len(pts) < 2:
self.upper = pts[:]
self.lower = pts[:]
return
upper, lower = [], []
for p in pts:
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) >= 0:
upper.pop()
upper.append(p)
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
self.upper = upper
self.lower = lower
def add(self, x, y):
from bisect import insort
p = (x, y)
insort(self.points, p)
self._rebuild()
def _y_on_hull(self, hull, x):
xs = [p[0] for p in hull]
if x < xs[0] or x > xs[-1]:
return None
idx = bisect_right(xs, x) - 1
if idx >= len(hull) - 1:
return hull[-1][1] if xs[-1] == x else None
if xs[idx] == x:
return hull[idx][1]
x1, y1 = hull[idx]
x2, y2 = hull[idx + 1]
# 線形補間（整数比較のため分数で）
# y = y1 + (y2-y1)*(x-x1)/(x2-x1)
return y1 + (y2 - y1) * (x - x1) / (x2 - x1)
def contains(self, x, y):
if len(self.points) < 3:
return False
hull_xs = [p[0] for p in self.upper]
if x < hull_xs[0] or x > hull_xs[-1]:
return False
uy = self._y_on_hull(self.upper, x)
ly = self._y_on_hull(self.lower, x)
if uy is None or ly is None:
return False
return ly - 1e-9 <= y <= uy + 1e-9
def solve():
N, Q = map(int, input().split())
init_pts = []
for _ in range(N):
x, y = map(int, input().split())
init_pts.append((x, y))
dch = DynamicConvexHull(init_pts)
out = []
for _ in range(Q):
line = input().split()
x, y = int(line[1]), int(line[2])
if line[0] == 'add':
dch.add(x, y)
else:
out.append('YES' if dch.contains(x, y) else 'NO')
print('\n'.join(out))
solve()Step-by-Step 解説
Step 1: Upper Hull と Lower Hull の定義
Upper Hull は「点群の最も上側の境界」: $x$ が増加するにつれ「右折りのみ」（時計回り）。Lower Hull は「最も下側の境界」: 「左折りのみ」（反時計回り）。
Step 2: 凸包の再構築（シンプル版）
点を追加するたびに Andrew's Monotone Chain を全点で実行（$O(N \log N)$）。高速版は sortedcontainers を用いて $O(\log^2 N)$ で更新できる。
Step 3: 内部判定
- $x$ が凸包の $x$ 範囲外 → NO
- Upper Hull で $x$ における $y$ の上限 $y_U$ を二分探索で計算
- Lower Hull で $y$ の下限 $y_L$ を計算
- $y_L \le y \le y_U$ → YES
Step 4: 整数座標での注意
線形補間で浮動小数点誤差が生じる。厳密判定には cross product を直接使う: クエリ点が各辺の「正しい側」にあるか $O(\log N)$ で確認。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 浮動小数点誤差 | 線形補間で整数比較が狂う | cross product で厳密判定（整数演算） |
| 凸包の境界判定 | < vs <= の混在 |
問題定義に従い境界を内部に含むか確認 |
| 点数が3未満 | 三角形未満で凸包が定義されない | 特殊ケース処理（点・線分の場合を別処理） |
次のステップ
発展問題: 動的凸包上での接線クエリ（ある外部点から凸包への接線の2頂点を $O(\log^2 N)$ で求めよ）。ヒント: Upper/Lower Hull それぞれで「cross product の符号変化」を二分探索する。