当前没有测试数据。

G - 多边形和点

得分：600分

问题描述

在二维坐标平面上，存在一个凸多边形$S$，其中正$x$轴指向右，正$y$轴指向上。$S$的顶点按逆时针顺序给出，具有坐标$(X_1,Y_1),\ldots,(X_N,Y_N)$。

对于每个点$(A_i,B_i)$，回答以下问题：该点在$S$内部、外部还是在$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$是一个严格凸多边形，即其内角都小于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$行应该包含 IN 表示$(A_i,B_i)$在$S$内部（且不在边界上），OUT表示在$S$外部（且不在边界上），以及 ON 表示在$S$的边界上。

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

ON
IN
OUT

下面的图示显示了$S$和给定的三个点。第一个点在$S$的边界上，第二个点在$S$内部，第三个点在$S$外部。

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

ON
ON
ON