← 返回题目列表

AtCoder · abc296_g

G. 多边形和点

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一个凸 N-gon S 在二维坐标平面中,其中正 x- 轴指向右侧且正方向 y- 轴指向上方。的顶点 S 有坐标 (X_1,Y_1),\ldots,(X_N,Y_N) 按逆时针顺序。

对于每个 Q 点 (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-gon。也就是说,它的内角都小于 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 if (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