配点: 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} 左右,但这些点位于多边形之外。