#abc296g. G - Polygon and Points

G - Polygon and Points

Score : 600600 points

问题陈述

在二维坐标平面上有一个凸 NN 边形 SS,其中正 xx 轴指向右侧,正 yy 轴指向上方。SS 的顶点按照逆时针顺序依次为 (X1,Y1),,(XN,YN)(X_1,Y_1),\ldots,(X_N,Y_N)

对于 QQ 个点 (Ai,Bi)(A_i,B_i),回答以下问题:这些点位于 SS 的内部、外部还是边界上?

以上为通义千问 qwen-max 翻译,仅供参考。

Problem Statement

There is a convex NN-gon SS in the two-dimensional coordinate plane where the positive xx-axis points to the right and the positive yy-axis points upward. The vertices of SS have the coordinates (X1,Y1),,(XN,YN)(X_1,Y_1),\ldots,(X_N,Y_N) in counter-clockwise order.

For each of QQ points (Ai,Bi)(A_i,B_i), answer the following question: is that point inside or outside or on the boundary of SS?

Constraints

  • 3N2×1053 \leq N \leq 2\times 10^5
  • 1Q2×1051 \leq Q \leq 2\times 10^5
  • 109Xi,Yi,Ai,Bi109-10^9 \leq X_i,Y_i,A_i,B_i \leq 10^9
  • SS is a strictly convex NN-gon. That is, its interior angles are all less than 180180 degrees.
  • (X1,Y1),,(XN,YN)(X_1,Y_1),\ldots,(X_N,Y_N) are the vertices of SS in counter-clockwise order.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

NN

X1X_1 Y1Y_1

\vdots

XNX_N YNY_N

QQ

A1A_1 B1B_1

\vdots

AQA_Q BQB_Q

Output

Print QQ lines. The ii-th line should contain IN if (Ai,Bi)(A_i,B_i) is inside SS (and not on the boundary), OUT if it is outside SS (and not on the boundary), and ON if it is on the boundary of SS.

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 SS and the given three points. The first point is on the boundary of SS, the second is inside SS, and the third is outside SS.

Figure

Sample Input 2

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

Sample Output 2

ON
ON
ON

update @ 2024/3/10 12:19:00