102966: [Atcoder]ABC296 G - Polygon and Points
Description
Score : $600$ points
Problem Statement
There is a convex $N$-gon $S$ in the two-dimensional coordinate plane where the positive $x$-axis points to the right and the positive $y$-axis points upward. The vertices of $S$ have the coordinates $(X_1,Y_1),\ldots,(X_N,Y_N)$ in counter-clockwise order.
For each of $Q$ points $(A_i,B_i)$, answer the following question: is that point inside or outside or on the boundary of $S$?
Constraints
- $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$ is a strictly convex $N$-gon. That is, its interior angles are all less than $180$ degrees.
- $(X_1,Y_1),\ldots,(X_N,Y_N)$ are the vertices of $S$ in counter-clockwise order.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $X_1$ $Y_1$ $\vdots$ $X_N$ $Y_N$ $Q$ $A_1$ $B_1$ $\vdots$ $A_Q$ $B_Q$
Output
Print $Q$ lines. The $i$-th line should contain IN if $(A_i,B_i)$ is inside $S$ (and not on the boundary), OUT if it is outside $S$ (and not on the boundary), and ON if it is on the boundary of $S$.
Sample Input 1
4 0 4 -2 2 -1 0 3 1 3 -1 3 0 2 2 0
Sample Output 1
ON IN OUT
The figure below shows $S$ and the given three points. The first point is on the boundary of $S$, the second is inside $S$, and the third is outside $S$.
Sample Input 2
3 0 0 1 0 0 1 3 0 0 1 0 0 1
Sample Output 2
ON ON ON
Input
题意翻译
在平面直角坐标系上给定一个 $n$ 个点的凸多边形，顶点均为整点，并按照逆时针顺序给出。 接下来有 $Q$ 个询问，每个询问给出一个整点，输出其是在多边形内部、外部或是边上。 Translated by @[Zealous_YH](https://www.luogu.com.cn/user/399150)Output
IN，如果$(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的外部。