← 返回题目列表

AtCoder · math_and_algorithm_bu

098. 多边形和点

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

配点: 1000 点

問題文

N 点 P_1, P_2, \dots, P_N 的多边形。点 P_i 的坐标是 (X_i, Y_i) 和P_i 和 按字典顺序比较 P_{i+1} 的线段 (i = 1, 2, \dots, N-1) 是多边形的边。另外, 连接P_N 和 按字典顺序比较 P_1 的线段也是多边形的边。 编写一个程序来确定

座標 (A, B) 是否包含在多边形内部。

制約

  • 3 \leq N \leq 100000
  • -10^9 \leqq X_i \leqq 10^9
  • -10^9 \leqq Y_i \leqq 10^9
  • -10^9 \leqq A \leqq 10^9
  • -10^9 \leqq B \leqq 10^9
  • 点 (A, B) 不在多边形的边上
  • 多边形的内角恰好是 它永远不会成为 180^{\circ} 如果
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
A B

出力

座標 (A, B) 包含在多边形内部 INSIDE,如果包含在外部 OUTSIDE 。

部分点

在这道题中,如果在多边形是凸多边形的所有情况下都正确回答,它将成为部分点。 500 赚取积分。


入力例 1

4
0 0
3 1
2 3
0 3
2 1

出力例 1

INSIDE

多边形应如下图所示,坐标 点 (2, 1) 包含在其中。


入力例 2

4
3 1
0 0
0 3
2 3
3 2

出力例 2

OUTSIDE

多边形应如下图所示,坐标 点 (3, 2) 点位于其外部。


入力例 3

6
5 5
-1 -3
5 1
-3 -5
1 1
-5 -3
0 -1

出力例 3

INSIDE

多边形应如下图所示,坐标 点 (0, -1) 包含在其中。


入力例 4

16
0 0
8 0
8 7
7 7
7 1
1 1
1 6
5 6
5 3
3 3
3 5
2 5
2 2
6 2
6 7
0 7
4 4

出力例 4

OUTSIDE

多边形应如下图所示,坐标 点 (4, 4) 点位于其外部。


入力例 5

3
0 0
1000000000 671903261
671903261 1000000000
520908341 350000013

出力例 5

OUTSIDE

在这个输入示例中,点和多边形非常接近,并且距离 虽然仅相距 10^{-9} 左右,但这些点位于多边形之外。