题目描述

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

$Q$ 個の点 $(A_i,B_i)$ について、それぞれ $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 と出力せよ。

题目大意

在平面直角坐标系上给定一个 $n$ 个点的凸多边形，顶点均为整点，并按照逆时针顺序给出。

接下来有 $Q$ 个询问，每个询问给出一个整点，输出其是在多边形内部、外部或是边上。

Translated by

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

ON
IN
OUT

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

ON
ON
ON

提示

制約

• $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$ の頂点を反時計回りに列挙したものである。
• 入力は全て整数である。

Sample Explanation 1

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