問題
反時計回り（CCW）に頂点が与えられた凸多角形（頂点数 $N$）がある。$Q$ 個のクエリ点それぞれについて、その点が多角形の内部または境界上にあるかを判定せよ（境界上も内側として Yes）。
頂点 $P_0$ を固定し、$P_0$ から各頂点への方向ベクトルでできる扇形の中から、クエリ点がどの三角形 $(P_0,P_k,P_{k+1})$ に属するかを二分探索で特定し、各クエリを $O(\log N)$ で処理せよ。
入力形式
N
x_1 y_1
...
x_N y_N
Q
qx_1 qy_1
...
qx_Q qy_Q制約
$3 \le N \le 2\times10^5$
$1 \le Q \le 2\times10^5$
座標の絶対値は $10^9$ 以下
多角形は狭義凸・CCW順
入出力例
入力例1
4
0 0
4 0
4 4
0 4
6
2 2
5 5
0 0
4 2
2 4
-1 2出力例1
Yes
No
Yes
Yes
Yes
No概念図
ヒント（段階的開示）
ヒント1（方向性）
毎クエリ全頂点との外積を調べれば$O(N)$で判定できるが、$Q$個で合計$O(NQ)$になり間に合わない。凸多角形の頂点が角度順に並んでいることを使えば二分探索で絞り込めるはずである。
ヒント2（アプローチ）
$P_0$から他の頂点への方向ベクトルは角度順に単調に並んでいる。クエリ点への方向ベクトルがどの2つの隣接頂点方向の「間」にあるかを外積の符号だけで二分探索できる。範囲が絞れたら最後にその三角形の内部判定を1回行う。
ヒント3（誘導）
def contains(pt):
if cross(P0, poly[1], pt) < 0 or cross(P0, poly[-1], pt) > 0:
return False # 扇形の外側
lo, hi = 1, N - 1
while hi - lo > 1:
mid = (lo + hi) // 2
if cross(P0, poly[mid], pt) >= 0:
lo = mid
else:
hi = mid
return cross(poly[lo], poly[hi], pt) >= 0境界（頂点上・辺上）を Yes とするため、すべての比較を等号込み（>=0 / <=0）で統一する。
模範解答 (Python)
import sys
def main():
data = sys.stdin.buffer.read().split()
idx = 0
N = int(data[idx]); idx += 1
poly = []
for _ in range(N):
x = int(data[idx]); idx += 1
y = int(data[idx]); idx += 1
poly.append((x, y))
Q = int(data[idx]); idx += 1
queries = []
for _ in range(Q):
x = int(data[idx]); idx += 1
y = int(data[idx]); idx += 1
queries.append((x, y))
def cross(ax, ay, bx, by):
return ax * by - ay * bx
p0x, p0y = poly[0]
def vec(px, py, qx, qy):
return qx - px, qy - py
def contains(px, py):
if (px, py) == (p0x, p0y):
return True
v1x, v1y = vec(p0x, p0y, poly[1][0], poly[1][1])
vpx, vpy = vec(p0x, p0y, px, py)
if cross(v1x, v1y, vpx, vpy) < 0:
return False
vnx, vny = vec(p0x, p0y, poly[N - 1][0], poly[N - 1][1])
if cross(vnx, vny, vpx, vpy) > 0:
return False
lo, hi = 1, N - 1
while hi - lo > 1:
mid = (lo + hi) // 2
vmx, vmy = vec(p0x, p0y, poly[mid][0], poly[mid][1])
if cross(vmx, vmy, vpx, vpy) >= 0:
lo = mid
else:
hi = mid
ax, ay = poly[lo]
bx, by = poly[hi]
ex, ey = vec(ax, ay, bx, by)
fx, fy = vec(ax, ay, px, py)
return cross(ex, ey, fx, fy) >= 0
out = []
for (px, py) in queries:
out.append("Yes" if contains(px, py) else "No")
print("\n".join(out))
main()Step-by-Step 解説
1扇形の外側を高速に除外
$P_0\to P_1$と$P_0\to P_{N-1}$の外側にクエリ点があれば、2回の外積計算だけで多角形の外だと即座に判定できる。
$P_0\to P_1$と$P_0\to P_{N-1}$の外側にクエリ点があれば、2回の外積計算だけで多角形の外だと即座に判定できる。
2角度順の単調性で二分探索
$P_0$から各頂点への方向ベクトルは反時計回りに単調に回転しているため、
$P_0$から各頂点への方向ベクトルは反時計回りに単調に回転しているため、
cross(P0→P_mid, P0→Q)の符号だけで二分探索が成立する。3最終確認は三角形1つだけ
絞り込んだ範囲$[lo,hi]$（$hi=lo+1$）の三角形について、辺$P_{lo}\to P_{hi}$に対する外積の符号で内外が確定する。
絞り込んだ範囲$[lo,hi]$（$hi=lo+1$）の三角形について、辺$P_{lo}\to P_{hi}$に対する外積の符号で内外が確定する。
4境界条件を等号込みで統一
頂点上・辺上のケースをすべて
頂点上・辺上のケースをすべて
Yesとするため、扇形判定・二分探索・最終判定のすべてを>=0 / <=0で統一する。5計算量
前処理不要で各クエリは外積計算$O(\log N)$回のみなので、全体で$O(Q\log N)$になる。
前処理不要で各クエリは外積計算$O(\log N)$回のみなので、全体で$O(Q\log N)$になる。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| $P_0$自身をクエリすると壊れる | 方向ベクトルが零ベクトルになり外積が常に0 | 最初にpt==P0を特別扱いしてTrueを返す |
| 二分探索の境界条件で無限ループ | lo<hiで書きmidの選び方を誤る | hi-lo>1を条件にし2頂点を確定させる |
| 不等号の等号を落とす | 境界上の点をすべてNoと誤判定 | すべての比較で等号を含める |
| 多角形が時計回り(CW)で誤判定 | 外積の符号の意味が反転する | 反時計回りを前提にするか、事前に向きを確認・反転する |
| 座標をfloatに変換してしまう | 誤差で境界判定がぶれる | Pythonのintは多倍長なので整数演算のまま扱う |
次のステップ
- 発展: 頂点の追加・削除がオンラインで発生する動的凸包でも同様の判定ができるよう、平衡二分探索木で頂点列を管理する設計を考えよ。
- 発展2: 「点から凸多角形への接線を求める」問題に拡張し、同じ二分探索の考え方が使えるか検証せよ。