AT_abc296_g [ABC296G] Polygon and Points
题目描述
在二维坐标平面上，$x$ 轴的正方向向右，$y$ 轴的正方向向上，有一个凸 $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`。
说明/提示
## 限制条件
- $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$ 的顶点，按逆时针顺序给出。
- 所有输入均为整数。
## 样例说明 1
$S$ 以及给定的 $3$ 个点如下图所示。第 $1$ 个点在 $S$ 的边界上，第 $2$ 个点在内部，第 $3$ 个点在外部。
由 ChatGPT 4.1 翻译