Points and Minimum Distance
Contest: Educational Codeforces Round 157 (Rated for Div. 2)
Difficulty rating: 800
Tags: greedy, math, sortings

You are given a sequence of integers $$$a$$$ of length $$$2n$$$. You have to split these $$$2n$$$ integers into $$$n$$$ pairs; each pair will represent the coordinates of a point on a plane. Each number from the sequence $$$a$$$ should become the $$$x$$$ or $$$y$$$ coordinate of exactly one point. Note that some points can be equal.

After the points are formed, you have to choose a path $$$s$$$ that starts from one of these points, ends at one of these points, and visits all $$$n$$$ points at least once.

The length of path $$$s$$$ is the sum of distances between all adjacent points on the path. In this problem, the distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is defined as $$$|x_1-x_2| + |y_1-y_2|$$$.

Your task is to form $$$n$$$ points and choose a path $$$s$$$ in such a way that the length of path $$$s$$$ is minimized.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of points to be formed.

The next line contains $$$2n$$$ integers $$$a_1, a_2, \dots, a_{2n}$$$ ($$$0 \le a_i \le 1\,000$$$) — the description of the sequence $$$a$$$.

Output format:
For each testcase, print the minimum possible length of path $$$s$$$ in the first line.

In the $$$i$$$-th of the following $$$n$$$ lines, print two integers $$$x_i$$$ and $$$y_i$$$ — the coordinates of the point that needs to be visited at the $$$i$$$-th position.

If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first testcase, for instance, you can form points $$$(10, 1)$$$ and $$$(15, 5)$$$ and start the path $$$s$$$ from the first point and end it at the second point. Then the length of the path will be $$$|10 - 15| + |1 - 5| = 5 + 4 = 9$$$.

In the second testcase, you can form points $$$(20, 20)$$$, $$$(10, 30)$$$, and $$$(10, 30)$$$, and visit them in that exact order. Then the length of the path will be $$$|20 - 10| + |20 - 30| + |10 - 10| + |30 - 30| = 10 + 10 + 0 + 0 = 20$$$.

Example input:
2
2
15 1 10 5
3
10 30 20 20 30 10

Example output:
9
10 1
15 5
20
20 20
10 30
10 30

Editorial:
Since the order of $$$a_i$$$ does not matter, let's sort them for convenience.
Let's treat the resulting path as two one-dimensional paths: one path $$$x_1 \rightarrow x_2 \rightarrow \dots \rightarrow x_n$$$ and one path $$$y_1 \rightarrow y_2 \rightarrow \dots \rightarrow y_n$$$. The length of the path $$$s$$$ is equal to the sum of lengths of these two paths.
If we fix which integers are $$$x$$$-coordinates and which integers are $$$y$$$-coordinates, it's quite easy to see that it is optimal to place both $$$[x_1, x_2, \dots, x_n]$$$ and $$$[y_1, y_2, \dots, y_n]$$$ in sorted order: the length of the path visiting both $$$\min x_i$$$ and $$$\max x_i$$$ should be at least $$$\max x_i - \min x_i$$$, and sorting gives exactly that result; the same with $$$y$$$-coordinates.
Okay, then, how do we choose which integers are $$$x$$$-coordinates and which integers are $$$y$$$-coordinates? The total length of the path $$$s$$$ will be equal to $$$\max x_i - \min x_i + \max y_i - \min y_i$$$; one of the minimums will be equal to the value of $$$a_1$$$; one of the maximums will be equal to the value of $$$a_{2n}$$$; so we need to consider the remaining minimum and maximum.
The minimum coordinate of any type should be less than or equal to at least $$$n - 1$$$ elements. Similarly, the maximum coordinate should be greater than or equal to at least $$$n-1$$$ elements. So, the second minimum (the minimum which is not $$$a_1$$$) is at most $$$a_{n+1}$$$, the second maximum is at least $$$a_n$$$, and the length of the path is at least $$$a_{2n} - a_1 + a_n - a_{n+1}$$$. And it is possible to reach this bound: take the first $$$n$$$ values in $$$a$$$ as $$$x$$$-coordinates, and the last $$$n$$$ values as $$$y$$$-coordinates.