102966: [Atcoder]ABC296 G - Polygon and Points

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

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$.

Figure


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

得分:600分 部分 问题描述 在二维坐标系中,正x轴指向右方,正y轴指向上方。有一个凸N边形S,顶点坐标为$(X_1,Y_1),\ldots,(X_N,Y_N)$,按逆时针顺序排列。 对于每个点$(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边形。也就是说,它的内角都小于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,如果$(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的外部。

Figure

样例输入 2 ``` 3 0 0 1 0 0 1 3 0 0 1 0 0 1 ``` 样例输出 2 ``` ON ON ON ```

加入题单

上一题 下一题 算法标签: