平面走査により、\(O((Q+N)\log(Q+N))\) や \(O(N+Q\log Q)\) などの計算量で解くことができます。

図：平面走査のイメージ

\(x\) 座標を固定した時、ある点が \(S\) の内部にあるかどうかを判定するには、\(S\) の高々 \(2\) つの辺との位置関係を調べれば良いです。\(x\) 座標の昇順に調べることで、調べるべき \(2\) つの辺を簡単に見つけることができます。

実装によっては \(y\) 軸に平行な辺が存在するケースに注意が必要です。

writer解(C++)

点と線分の位置関係について

点と直線(線分)の位置関係を調べる方法は、競技プログラミングにおいては内積と外積を用いる方法が一般的です。以下、\(2\) つのベクトル\(u,v\) に対し、内積を \(u\cdot v\)、外積を \(u\times v \) と表します。

線分 \(PQ\) と点 \(R\) について、次が成り立ちます。

• \(PQ\times PR>0\)のとき、点 \(R\) は \(P\) から \(Q\) を見る向きで左側にある
• \(PQ\times PR<0\) のとき、点 \(R\) は \(P\) から \(Q\) を見る向きで右側にある
• \(PQ \times PR =0 \) のとき、点 \(R\) は直線 \(PQ\) 上にある
  • \(PQ\cdot PR<0\) のとき、点 \(R\) は線分 \(PQ\) を \(P\) 側に延長した方向にある
  • \(0\leq PQ\cdot PR \leq PQ \cdot PQ\) のとき、点 \(R\) は線分 \(PQ\) 上にある
  • \(PQ\cdot PR > PQ \cdot PQ\) のとき、点 \(R\) は線分 \(PQ\) を \(Q\) 側に延長した方向にある

この方法が用いられることが多い理由の1つは、誤差がないことです。浮動小数点数を使う場合は誤差に注意する必要がありますが、外積及び内積の計算は点の座標が整数であれば整数の範囲で行うことができるため、誤差の心配はありません。

外積について

定義：
\(3\) 次元ベクトル空間内の \(2\) つのベクトル \(a,b\) の外積 \(a\times b\)を、\(a,b\) の両方に垂直で、右ねじの向き(図参照)を持ち、\(a,b\) のなす平行四辺形の面積に等しい大きさを持つベクトルと定める。

(画像はwikipediaより引用)

外積の性質：
\((a_1,a_2,a_3)\times(b_1,b_2,b_3)=(a_2b_3-a_3b_2,a_3b_1-a_1b_3,a_1b_2-a_2b_1)\) である。

2次元ベクトルの”外積”：
2つの2次元ベクトル \(a=(a_1,a_2),b=(b_1,b_2)\) のなす平行四辺形の符号付き面積 \(a_1b_2-a_2b_1\) を、\(a,b\) の外積という。
これは2つの3次元ベクトルの外積 \((a_1,a_2,0)\times(b_1,b_2,0)=(0,0,a_1b_2-a_2b_1)\) の第3成分である。

2次元ベクトルに対する外積はプログラミング分野において慣用的に用いられている表現であり、数学分野では一般的なものではないことに注意してください。

内積について

定義：
\(n\) 次元ベクトル空間内の2つのベクトル \((a_1,\ldots.a_n),(b_1,\ldots,b_n)\) に対し、(標準)内積 \(a\cdot b\) を、値 \( a_1b_1+a_2b_2+\ldots+a_nb_n\) と定める。

内積の性質：
2つのベクトル \(a,b\) の内積は、\(b\) を \(a\) に射影したベクトルの向き付きの大きさと、\(a\) の大きさの積に等しい。