Вам задана последовательность целых чисел $$$a$$$ длины $$$2n$$$. Вам нужно разбить эти $$$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$$$.
В $$$i$$$-ю из следующих $$$n$$$ строк выведите два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты точки, которую нужно посетить $$$i$$$-й по счету.
Если есть несколько ответов, выведите любой из них.
2215 1 10 5310 30 20 20 30 10
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$$$.
Название |
---|