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。

输入输出样例 #1

输入 #1

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

输出 #1

ON
IN
OUT

输入输出样例 #2

输入 #2

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

输出 #2

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$ 的顶点，按逆时针顺序给出。
• 所有输入均为整数。

样例说明 1

$S$ 以及给定的 $3$ 个点如下图所示。第 $1$ 个点在 $S$ 的边界上，第 $2$ 个点在内部，第 $3$ 个点在外部。

由 ChatGPT 4.1 翻译