← 返回题目列表

Codeforces · 1237/C1

C1. 平衡移除(更简单)

中文机器翻译题面 查看原题

这是问题的一个更简单的版本。在此版本中,$$$n \le 2000$$$。

三维空间中有 $$$n$$$ 个不同的点,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 个点的坐标为 $$$(x_i, y_i, z_i)$$$。点数 $$$n$$$ 是偶数。

您想要使用一系列 $$$\frac{n}{2}$$$ 捕捉来删除所有 $$$n$$$ 点。只需轻轻一击,您就可以删除尚未删除的任意两个点 $$$a$$$ 和 $$$b$$$,并形成完美平衡的一对。如果没有其他点 $$$c$$$(尚未删除)位于点 $$$a$$$ 和 $$$b$$$ 的轴对齐最小边界框内,则一对点 $$$a$$$ 和 $$$b$$$ 完美平衡。

形式上,点 $$$c$$$ 位于点 $$$a$$$ 和 $$$b$$$ 的轴对齐最小边界框内当且仅当 $$$\min(x_a, x_b) \le x_c \le \max(x_a, x_b)$$$, $$$\min(y_a, y_b) \le y_c \le \max(y_a, y_b)$$$ 和 $$$\min(z_a, z_b) \le z_c \le \max(z_a, z_b)$$$。请注意,边界框可能会退化。

找到一种方法来删除 $$$\frac{n}{2}$$$ 快照中的所有点。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2000$$$;$$$n$$$ 为偶数),表示点数。

接下来的 $$$n$$$ 行包含三个整数 $$$x_i$$$, $$$y_i$$$, $$$z_i$$$ ($$$-10^8 \le x_i, y_i, z_i \le 10^8$$$),表示第 $$$i$$$ 个点的坐标。

没有两点重合。

输出

输出 $$$\frac{n}{2}$$$ 整数对 $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$),表示在快照 $$$i$$$ 上删除的点的索引。 $$$1$$$ 和 $$$n$$$(含)之间的每个整数必须在输出中恰好出现一次。

我们可以证明总是可以删除所有点。如果有多个解,则输出任意一个。

示例

输入 #1

6
3 1 0
0 3 0
2 2 0
1 0 0
1 3 0
0 1 0

输出 #1

3 6
5 1
2 4

输入 #2

8
0 1 1
1 0 1
1 1 0
1 1 1
2 2 2
3 2 2
2 3 2
2 2 3

输出 #2

4 5
1 6
2 7
3 8

注意

在第一个示例中,点及其相应的边界框如下所示(为简单起见,以二维绘制,因为所有点都位于 $$$z = 0$$$ 平面上)。请注意删除的顺序很重要:例如,点 $$$5$$$ 和 $$$1$$$ 最初并不形成完美平衡的对,但在点 $$$3$$$ 被删除后它们就会形成完美平衡的对。