多边形与点

题目描述

在二维坐标平面上有一个凸 $N$ 边形 $S$，其中 $x$ 轴正方向朝右，$y$ 轴正方向朝上。$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；如果在 $S$ 外部（且不在边界上）则输出 OUT；如果在 $S$ 的边界上则输出 ON。

样例

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

ON
IN
OUT

第一个点在 $S$ 的边界上，第二个点在 $S$ 内部，第三个点在 $S$ 外部。

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

ON
ON
ON

数据范围

• $3 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $-10^9 \le X_i,Y_i,A_i,B_i \le 10^9$
• $S$ 是严格凸的 $N$ 边形。即，它的内角都小于 $180$ 度。
• $(X_1,Y_1),\ldots,(X_N,Y_N)$ 是 $S$ 的顶点，按逆时针顺序给出。
• 输入中的所有值都是整数。