分数: 600 点
问题陈述
有一个凸 N-gon S 在二维坐标平面中,其中正 x- 轴指向右侧且正方向 y- 轴指向上方。的顶点 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-gon。也就是说,它的内角都小于 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 if (A_i,B_i) 在里面 S (不在边界上), OUT 如果在室外 S (不在边界上),并且 ON 如果它在边界上 S.
样本输入 1
4 0 4 -2 2 -1 0 3 1 3 -1 3 0 2 2 0
示例输出 1
ON IN OUT
下图所示 S 并给出三点。第一个点位于 的边界上 S,第二个在里面 S,第三个在外面 S.

示例输入 2
3 0 0 1 0 0 1 3 0 0 1 0 0 1
示例输出 2
ON ON ON