CSES2192 点在多边形内
#CS2192. 点在多边形内
点在多边形内
题目背景
翻译自 CSES-2192 题。
题目描述
给定一个有 n 个顶点的多边形和一组 m 个点。你的任务是判断每个点是位于多边形内部、外部，还是在多边形的边界上。
这个多边形有 n 个顶点 (x1,y1),(x2,y2),…,(xn,yn)(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)(x1,y1),(x2,y2),…,(xn,yn)。对于每个 i=1,2,…,n−1i = 1, 2, \dots, n-1i=1,2,…,n−1，顶点 (xi,yi)(x_i, y_i)(xi,yi) 和 (xi+1,yi+1)(x_{i+1}, y_{i+1}) (xi+1,yi+1) 是相邻的，而顶点 (x1,y1)(x_1, y_1)(x1,y1) 和 (xn,yn)(x_n, y_n)(xn,yn) 也是相邻的。
输入格式
第一行输入两个整数 n 和 m：分别表示多边形的顶点数和点的数量。
接下来的 n 行，每行包含两个整数 xix_ixi 和 yi y_i yi，表示多边形的第 i 个顶点坐标。
接下来的 m 行，每行包含两个整数 x 和 y，表示一个点的坐标。
输出格式
对于每个点，输出 INSIDE、OUTSIDE 或 BOUNDARY。
-
INSIDE 表示该点位于多边形内部。
-
OUTSIDE 表示该点位于多边形外部。
-
BOUNDARY 表示该点在多边形的边界上。
样例
4 3
1 1
4 2
3 5
1 4
2 3
3 1
1 3
INSIDE
OUTSIDE
BOUNDARY
说明/提示
−109≤xi,yi≤109-10^9 \leq x_i, y_i \leq 10^9−109≤xi,yi≤109;