G - Polygon and Points Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

x 軸の正の向きを右、y 軸の正の向きを上とする 2 次元座標平面上に、凸 N 角形 S があります。S の頂点の座標は、反時計回りに (X_1,Y_1),\ldots,(X_N,Y_N) です。

Q 個の点 (A_i,B_i) について、それぞれ S の内部・外部・境界上のいずれにあるか求めてください。

制約

  • 3 \leq N \leq 2\times 10^5
  • 1 \leq Q \leq 2\times 10^5
  • -10^9 \leq X_i,Y_i,A_i,B_i \leq 10^9
  • S は狭義凸 N 角形である。すなわち、全ての内角は 180 度未満である。
  • (X_1,Y_1),\ldots,(X_N,Y_N) は S の頂点を反時計回りに列挙したものである。
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
X_1 Y_1
\vdots
X_N Y_N
Q
A_1 B_1
\vdots
A_Q B_Q

出力

Q 行出力せよ。i 行目には、(A_i,B_i) が S の内部(境界含まず)にあるとき IN、外部(境界含まず)にあるとき OUT、境界上にあるとき ON と出力せよ。

入力例 1

4
0 4
-2 2
-1 0
3 1
3
-1 3
0 2
2 0

出力例 1

ON
IN
OUT

S 及び 与えられた 3 個の点は下図の通りです。1 番目の点は S の境界上、2 番目の点は内部、3 番目の点は外部にあります。

図

入力例 2

3
0 0
1 0
0 1
3
0 0
1 0
0 1

出力例 2

ON
ON
ON

Score : 600 points

Problem Statement

There is a convex N-gon S in the two-dimensional coordinate plane where the positive x-axis points to the right and the positive y-axis points upward. The vertices of S have the coordinates (X_1,Y_1),\ldots,(X_N,Y_N) in counter-clockwise order.

For each of Q points (A_i,B_i), answer the following question: is that point inside or outside or on the boundary of S?

Constraints

  • 3 \leq N \leq 2\times 10^5
  • 1 \leq Q \leq 2\times 10^5
  • -10^9 \leq X_i,Y_i,A_i,B_i \leq 10^9
  • S is a strictly convex N-gon. That is, its interior angles are all less than 180 degrees.
  • (X_1,Y_1),\ldots,(X_N,Y_N) are the vertices of S in counter-clockwise order.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
X_1 Y_1
\vdots
X_N Y_N
Q
A_1 B_1
\vdots
A_Q B_Q

Output

Print Q lines. The i-th line should contain IN if (A_i,B_i) is inside S (and not on the boundary), OUT if it is outside S (and not on the boundary), and ON if it is on the boundary of S.

Sample Input 1

4
0 4
-2 2
-1 0
3 1
3
-1 3
0 2
2 0

Sample Output 1

ON
IN
OUT

The figure below shows S and the given three points. The first point is on the boundary of S, the second is inside S, and the third is outside S.

Figure

Sample Input 2

3
0 0
1 0
0 1
3
0 0
1 0
0 1

Sample Output 2

ON
ON
ON