Day 156-Q5 — 非凸多角形の点包含判定（Winding Number・回転数）

2026-09-17 赤色 Master / Phase 8+ ★★★★★★★★★ 整数演算のみ・向き不問・nonzero 規則

問題

$N$ 頂点の多角形 $P_1,\dots,P_N$（この順に辺で結ばれ $P_N$ と $P_1$ も結ばれる。凸とは限らない。辺同士は端点以外で交わらないが、向きは時計回り・反時計回りのどちらでもよい）と $Q$ 個の点が与えられる。各点について内部なら IN、辺上なら ON、外部なら OUT を出力せよ。

入力形式

N
x_1 y_1
...
x_N y_N
Q
px_1 py_1
...
px_Q py_Q

制約

変数範囲補足
$N$$3\le N\le2000$単純多角形（自己交差なし）
$Q$$1\le Q\le2000$$O(NQ)=4\times10^6$ で素朴解が通る
座標$|x|,|y|\le10^9$ の整数外積は $10^{18}$ 規模（Python は多倍長で安全）

入出力例

入力例1

8
0 0
6 0
6 2
2 2
2 4
6 4
6 6
0 6
7
1 3
4 3
3 1
6 3
2 3
7 7
3 5

出力例1

IN
OUT
IN
OUT
ON
OUT
IN

「C」の字型。$(4,3)$ は凹んだ内側で外部、$(2,3)$ は凹みの縦辺上、$(6,3)$ は開口部で外部。

概念図：C 字型多角形と 7 つのクエリ点（実測結果）

水平線 y=3 上向き辺・点は左 → +1 (1,3) IN wn=1 (4,3) OUT wn=0 (3,1) IN (6,3) OUT (2,3) ON (7,7) OUT (3,5) IN 頂点列を逆順（時計回り）にすると (1,3) の wn は −1（実測）。 判定は wn≠0 なので IN のまま。 乱択 5000 点で交差数法と全件一致

ヒント（段階的開示）

ヒント1（方向性）

凸多角形なら「すべての辺について点が左側か」で判定できた（Day 136）が、非凸では使えない。代わりに「点から見て境界を一周したとき、境界が点の周りを何回まわるか」（回転数）を考える。外部の点では正味 0 回、内部では $\pm1$ 回。

ヒント2（アプローチ）

回転数は角度を積分しなくても、各辺が「点を通る水平線」を上向きに横切るか下向きに横切るかを数えるだけで求まる。$a_y\le p_y<b_y$（上向き）かつ点が辺の左側なら +1、$b_y\le p_y<a_y$（下向き）かつ点が右側なら −1。左右は外積 $\mathrm{cross}(b-a,p-a)$ の符号。整数座標なら浮動小数点は一切不要。

ヒント3（誘導） 
wn = 0
for i in range(n):
    a, b = poly[i], poly[(i+1) % n]
    if on_segment(p, a, b): return "ON"
    if a[1] <= p[1]:
        if b[1] > p[1] and cross(a, b, p) > 0: wn += 1   # 上向き横断・点は左
    else:
        if b[1] <= p[1] and cross(a, b, p) < 0: wn -= 1  # 下向き横断・点は右
return "IN" if wn != 0 else "OUT"

模範解答 (Python)

import sys

def cross(ox, oy, ax, ay, bx, by):
    return (ax - ox) * (by - oy) - (ay - oy) * (bx - ox)

def on_segment(px, py, ax, ay, bx, by):
    # 共線 かつ 座標範囲内（整数演算のみ）
    return (cross(ax, ay, bx, by, px, py) == 0
            and min(ax, bx) <= px <= max(ax, bx)
            and min(ay, by) <= py <= max(ay, by))

def classify(poly, px, py):
    """回転数(winding number)で IN / ON / OUT を返す。向きは問わない"""
    n = len(poly)
    wn = 0
    for i in range(n):
        ax, ay = poly[i]
        bx, by = poly[(i + 1) % n]
        if on_segment(px, py, ax, ay, bx, by):
            return "ON"
        if ay <= py:
            # 辺が上向きに水平線 y=py を横切り、点が辺の左側なら +1
            if by > py and cross(ax, ay, bx, by, px, py) > 0:
                wn += 1
        else:
            # 辺が下向きに横切り、点が辺の右側なら -1
            if by <= py and cross(ax, ay, bx, by, px, py) < 0:
                wn -= 1
    return "IN" if wn != 0 else "OUT"

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    poly = []
    for _ in range(n):
        poly.append((int(data[idx]), int(data[idx + 1]))); idx += 2
    q = int(data[idx]); idx += 1
    out = []
    for _ in range(q):
        px, py = int(data[idx]), int(data[idx + 1]); idx += 2
        out.append(classify(poly, px, py))
    print("\n".join(out))

main()

Step-by-Step 解説

1半開区間 $a_y\le p_y<b_y$ が頂点を正しく扱う
点と同じ高さに頂点があるとき、頂点を共有する 2 辺の両方を数えると二重カウント。「下端は含み上端は含まない」半開区間にすると頂点は上側の辺だけで 1 回数えられる（極大・極小なら 0 回か 2 回で打ち消す）。
2実測（C 字型・本ページ作成時に Python で実行）
点$wn$判定交差数（even–odd）法
(1,3)1ININ
(4,3)0OUT（凹みの中）OUT
(3,1)1ININ
(6,3)0OUT（開口部）OUT
(2,3)—ONON
(7,7)0OUTOUT
(3,5)1ININ
$-1\le x,y\le7$ の格子点を乱択 5000 回試して交差数法と全件一致（不一致 0）。逆順（時計回り）にすると (1,3) の $wn=-1$ だが判定は wn != 0 なので IN のまま——向きを揃える前処理が不要。
3両手法が「違う答え」を出す場合（自己交差多角形）
五芒星（半径 100 の円周上を丸めた $(0,100),(-59,-81),(95,31),(-95,31),(59,-81)$）の中心 $(0,0)$ では
手法中心 (0,0)先端付近 (0,50)
回転数法（nonzero）$wn=2$ → IN$wn=1$ → IN
交差数法（even–odd）交差 2 回 → OUTIN
本問の制約（辺は端点以外で交わらない）を外すと規則の選択で答えが変わる。SVG の fill-rule="nonzero" / "evenodd" がこの 2 つに対応する。

迷った他案と採らなかった理由

案採否理由
角度の総和（atan2 の差分を足して $2\pi$ で割る）却下浮動小数点の累積誤差で $wn\approx0.9999$ となり閾値判定が必要。$10^9$ 座標では危険
交差数（even–odd）法同等・不採用単純多角形では等価で実装量も同じ。Step 3 の差異を示すため回転数法を主に据えた
凸分割してから凸判定却下前処理 $O(N\log N)$〜$O(N^2)$ で各判定 $O(\log N)$ になるが、$N,Q\le2000$ では $O(NQ)$ で十分。$Q\ge10^6$ なら判断が変わる（スラブ分割など）

よくあるミス

ミス原因正しい書き方
$a_y\le p_y\le b_y$ と閉区間にして頂点を二重カウント2 辺の両方が条件を満たす下端含む・上端含まない半開区間
外積の符号だけで左右を決め、辺の向きを見ない下向き辺では左右が逆転上向きは cross > 0 で +1、下向きは cross < 0 で −1
ON 判定を後回しにする辺上の点は横断判定が不定各辺で最初に on_segment を確認し即 ON
浮動小数点で交点の $x$ を計算$10^9$ 座標同士の除算で誤差外積の符号比較だけで済ませる

次のステップ

  • 関連する実問題: AOJ CGL_3_C「Polygon–Point Containment」（同一の出力仕様）、ABC 296 G「Polygon and Points」（凸版・二分探索が必要）
  • 発展: 穴のある多角形——回転数は閉路ごとの和で自然に拡張でき、穴の向きを外周と逆にする GIS の慣行と nonzero 規則の関係を確認する
  • 扱わなかった範囲: $Q\sim10^6$ の前処理型（スラブ・台形分割）、自己交差多角形でどちらの規則を採るかの仕様判断
  • 次回予告: 次セッションで別テーマへ

自己評価

自分の回答

気づき・メモ