← 返回题目列表

Codeforces · 1895/B

B. 点和最小距离

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

给你一个长度为$$$2n$$$的整数序列$$$a$$$。您必须将这些 $$$2n$$$ 整数拆分为 $$$n$$$ 对;每对将代表平面上一个点的坐标。序列 $$$a$$$ 中的每个数字都应该恰好成为一个点的 $$$x$$$ 或 $$$y$$$ 坐标。请注意,某些点可以相等。

点形成后,你必须选择一条路径$$$s$$$,从这些点之一开始,到这些点之一结束,并至少访问所有$$$n$$$点一次。

路径 $$$s$$$ 的长度是路径上所有相邻点之间的距离之和。在此问题中,两点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 之间的距离定义为 $$$|x_1-x_2| + |y_1-y_2|$$$。

你的任务是形成$$$n$$$点并选择一条路径$$$s$$$,使得路径$$$s$$$的长度最小化。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 要形成的点数。

下一行包含 $$$2n$$$ 整数 $$$a_1, a_2, \dots, a_{2n}$$$ ($$$0 \le a_i \le 1\,000$$$) - 序列 $$$a$$$ 的描述。

输出

对于每个测试用例,在第一行中打印路径 $$$s$$$ 的最小可能长度。

在接下来的 $$$n$$$ 行的第 $$$i$$$ 行中,打印两个整数 $$$x_i$$$ 和 $$$y_i$$$ — 第 $$$i$$$ 位置需要访问的点的坐标。

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

示例

输入 #1

2
2
15 1 10 5
3
10 30 20 20 30 10

输出 #1

9
10 1
15 5
20
20 20
10 30
10 30

注意

例如,在第一个测试用例中,您可以形成点 $$$(10, 1)$$$ 和 $$$(15, 5)$$$ 并从第一个点开始路径 $$$s$$$ 并在第二个点结束。那么路径的长度将为$$$|10 - 15| + |1 - 5| = 5 + 4 = 9$$$。

在第二个测试用例中,您可以形成点 $$$(20, 20)$$$、$$$(10, 30)$$$ 和 $$$(10, 30)$$$,并按照确切的顺序访问它们。那么路径的长度将为$$$|20 - 10| + |20 - 30| + |10 - 10| + |30 - 30| = 10 + 10 + 0 + 0 = 20$$$。