Point in Polygon

题目描述

给出一个有 n 个顶点的多边形和 m 个点的列表。你的任务是判断每个点是在多边形内部、外部还是在边界上。 多边形由 n 个顶点 $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ 组成。对于 i=1,2,\dots,n-1，顶点 $(x_i,y_i)$ 和 $(x_{i+1},y_{i+1})$ 是相邻的，且顶点 $(x_1,y_1)$ 和 $(x_n,y_n)$ 也是相邻的。

输入格式

第一行包含两个整数 n 和 m：多边形的顶点数和点的数量。 接下来有 n 行描述多边形。第 i 行包含两个整数 $x_i$ 和 $y_i$。 你可以假设多边形是简单的，即不自相交。 最后有 m 行描述这些点。每行包含两个整数 $x$ 和 $y$。

输出格式

对于每个点，输出 "INSIDE"、"OUTSIDE" 或 "BOUNDARY"。

4 3
1 1
4 2
3 5
1 4
2 3
3 1
1 3

INSIDE
OUTSIDE
BOUNDARY

提示

$3 \le n,m \le 1000$ $1 \le m \le 1000$ $-10^9 \le x_i, y_i \le 10^9$ $-10^9 \le x, y \le 10^9$

标签: CSES2192|几何

来源

CSES2192|几何