7419. 点在多边形内 (Point in Polygon)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 点在多边形内 (Point in Polygon) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 给你一个包含 $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`（边界）。 ## 输入输出样例 ### 输入 #1 ```text 4 3 1 1 4 2 3 5 1 4 2 3 3 1 1 3 ``` ### 输出 #1 ```text INSIDE OUTSIDE BOUNDARY ``` ## 说明/提示 ### 数据规模与约定 - $3 \le n \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$