← 返回题目列表

Codeforces · 2122/C

C. 曼哈顿对

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

您在 2D 平面上获得 $$$n$$$ 点 $$$(x_i, y_i)$$$,其中 $$$n$$$ 是偶数。选择 $$$\tfrac{n}{2}$$$ 不相交对 $$$(a_i, b_i)$$$ 最大化点对之间的曼哈顿距离总和。换句话说,最大化 $$\sum_{i=1}^{n/2} |x_{a_i} - x_{b_i}| + |y_{a_i} - y_{b_i}|.$$

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个偶数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — 点数。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^6 \le x_i, y_i \le 10^6$$$) — 第 $$$i$$$ 点的坐标。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$\tfrac{n}{2}$$$ 行,第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ - 第 $$$i$$$ 对中点的索引。

如果有多个解决方案,请打印其中任何一个。

示例

输入
复制

2
4
1 1
3 0
4 2
3 4
10
-1 -1
-1 2
-2 -2
-2 0
0 2
2 -3
-4 -4
-4 -2
0 1
-4 -2

输出
复制

4 1
2 3
8 1
9 10
7 5
2 3
6 4

注意

在第一个测试用例中,最佳解决方案是选择 $$$(1, 4)$$$ 和 $$$(2, 3)$$$ 对,从而实现距离总和 $$$5 + 3 = 8$$$。

在第二个测试用例中,最佳解决方案是选择 $$$(1, 8)$$$、$$$(9, 10)$$$、$$$(5, 7)$$$、$$$(2, 3)$$$、$$$(4, 6)$$$ 这对,其距离总和为 $$$4 + 7 + 10 + 5 + 7 = 33$$$。