Polygon and Points

题目描述

在二维坐标平面上有一个凸的 $N$ 边形 $S$，其中正 $x$ 轴指向右方，正 $y$ 轴指向上方。$S$ 的顶点按逆时针顺序的坐标为 $(X_1,Y_1),\ldots,(X_N,Y_N)$。 对于每个查询点 $(A_i,B_i)$，回答以下问题：该点是在 $S$ 的内部、外部还是在 $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

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$ 的顶点。 输入中的所有数值都是整数。下图展示了 $S$ 和给定的三个点。第一个点在 $S$ 的边界上，第二个在 $S$ 的内部，第三个在 $S$ 的外部。

标签: AtCoder|abc296G

来源

AtCoder|abc296G