链接: https://cses.fi/problemset/task/2192

板块: Geometry

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个由 $n$ 个顶点组成的多边形，以及 $m$ 个点的列表。你的任务是判断每个点是在多边形内部、外部还是边界上。

该多边形由 $n$ 个顶点 $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ 组成。顶点 $(x_i,y_i)$ 与 $(x_{i+1},y_{i+1})$ 相邻（$i=1,2,\dots,n-1$），并且顶点 $(x_1,y_1)$ 与 $(x_n,y_n)$ 也相邻。

输入

第一行输入包含两个整数 $n$ 和 $m$：多边形的顶点数以及点的数量。

接下来有 $n$ 行描述该多边形。第 $i$ 行包含两个整数 $x_i$ 和 $y_i$。

你可以假设该多边形是简单多边形，即它不与自身相交。

最后有 $m$ 行描述这些点。每行包含两个整数 $x$ 和 $y$。

输出

对每个点，输出 "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$

样例输入

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

样例输出

INSIDE
OUTSIDE
BOUNDARY