题目描述

:::align{center}

大小为 4 的 Voronoi 图。 :::

在二维笛卡尔坐标系中，我们将非空点集 $S$ 的 Voronoi 图 定义为按"该位置最接近集合 $S$ 中的哪个点？"这一准则划分平面的图形。更精确地说，给定非空点集 $\{P_1, P_2, \cdots, P_n\}$ 的 Voronoi 图是一个 区域 的集合：点 $K$ 包含在区域 $i$ 中当且仅当对于所有 $1 \le j \le n$ 有 $d(P_i, K) \le d(P_j, K)$，其中 $d(X, Y)$ 表示点 $X$ 和 $Y$ 之间的欧几里得距离。

例如，在上图中，平面上的每个位置都根据最接近的点着色。属于单个区域的点用浅色表示该区域，而属于多个区域的点形成黑色的线和点。

有一种算法可以在 $O(n \log(n))$ 时间内计算 Voronoi 图，但它以非常复杂和困难而闻名。实际上，我们是宽容的出题人，因此我们设定 $n \leq 2000$，这意味着你可以用较慢的 Voronoi 图算法解决这个任务！

在此任务中，你需要解决 Voronoi 图中的 点查询问题：在由点集 $\{P_1, P_2, \cdots, P_n\}$ 构建的 Voronoi 图中，你需要确定点属于哪个（哪些）区域。更精确地说，你将收到 $q$ 个点的查询。对于每个查询点，你需要确定以下内容：

• 如果它不包含在任何区域中，输出 NONE。
• 如果它恰好包含在一个区域中，输出 REGION X，其中 X 是该区域的索引。
• 如果它恰好包含在两个区域中，输出 LINE X Y，其中 X 和 Y（X $<$ Y）是这两个区域的索引。
• 如果它包含在三个或更多区域中，输出 POINT。

输入格式

第一行给出构成 Voronoi 图的点的数量 $n$ 和查询的数量 $q$（$3 \le n \le 2,000$，$1 \le q \le 250,000$）。

接下来的 $n$ 行中，第 $i$ 行给出两个整数，表示 $P_i$ 的 $x$ 和 $y$ 坐标。这些是构成 Voronoi 图的点。所有 $n$ 个点都是不同的（$|x|, |y| \le 10^4$）。

接下来的 $q$ 行中，第 $j$ 行给出两个整数，表示 $Q_j$ 的 $x$ 和 $y$ 坐标。对于每个点 $Q_j$，你应该确定给定点属于哪个（哪些）区域（$|x|, |y| \le 10^4$）。

输出格式

输出包含 $q$ 行。在第 $j$ 行，你应该输出以下之一：

• 如果 $Q_j$ 不包含在任何区域中，输出 NONE。
• 如果 $Q_j$ 恰好包含在一个区域中，输出 REGION X，其中 X 是该区域的索引。
• 如果 $Q_j$ 恰好包含在两个区域中，输出 LINE X Y，其中 X 和 Y（X $<$ Y）是这两个区域的索引。
• 如果 $Q_j$ 包含在三个或更多区域中，输出 POINT。

4 3
-5 0
0 5
3 4
1 -6
-2 2
0 0
2 2

LINE 1 2
POINT
REGION 3

提示

示例图如上所示。

翻译由 DeepSeek V3 完成