Chain Reaction
Contest: Codeforces Round 349 (Div. 1)
Difficulty rating: 3000
Tags: brute force, geometry

Group of Berland scientists, with whom you have a close business relationship, makes a research in the area of peaceful nuclear energy. In particular, they found that a group of four nanobots, placed on a surface of a plate, can run a powerful chain reaction under certain conditions.

To be precise, researchers introduced a rectangular Cartesian coordinate system on a flat plate and selected four distinct points with integer coordinates where bots will be placed initially. Next each bot will be assigned with one of the four directions (up, down, left or right) parallel to the coordinate axes. After that, each bot is shifted by an integer distance (which may be different for different bots) along its direction. The chain reaction starts, if the bots are in the corners of a square with positive area with sides parallel to the coordinate axes. Each corner of the square must contain one nanobot. This reaction will be stronger, if bots spend less time to move. We can assume that bots move with unit speed. In other words, the lesser is the maximum length traveled by bot, the stronger is reaction.

Scientists have prepared a set of plates and selected starting position for the bots for each plate. Now they ask you to assign the direction for each bot to move after landing such that the maximum length traveled by bot is as small as possible.

Input format:
The first line contains an integer number t (1 ≤ t ≤ 50) — the number of plates.

t descriptions of plates follow. A description of each plate consists of four lines. Each line consists of a pair of integers numbers xi, yi ( - 108 ≤ xi, yi ≤ 108) — coordinates of the next bot. All bots are in different locations.

Note, though, the problem can include several records in one test, you can hack other people's submissions only with the test of one plate, i.e. parameter t in a hack test should be equal to 1.

Output format:
Print answers for all plates separately. First goes a single integer number in a separate line. If scientists have made an unfortunate mistake and nanobots are not able to form the desired square, print -1. Otherwise, print the minimum possible length of the longest bot's path.

If a solution exists, in the next four lines print two integer numbers — positions of each bot after moving. Print bots' positions in the order they are specified in the input data.

If there are multiple solution, you can print any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
2
1 1
1 -1
-1 1
-1 -1
1 1
2 2
4 4
6 6

Example output:
0
1 1
1 -1
-1 1
-1 -1
-1

Editorial:
В задаче даны четыре точки на плоскости. Требуется подвигать каждую из них вверх, вниз, вправо или влево, чтобы получить квадрат со сторонами, параллельными осям координат. Нужно минимизировать максимальное расстояние, на которое будет сдвинута точка.
Переберём длину стороны квадрата d, положение нижней левой точки (x, y) (среди чего перебирать, будет видно позже). Кроме того, переберём перестановку точек так, чтобы первая перешла в нижнюю левую точку квадрата, вторая — в нижнюю правую и т.д. После этого несложно проверить, действительно ли из такой перестановки точек можно получить такой квадрат, и если да, посчитать максимальное перемещение. Остаётся вопрос, где перебирать d, x и y.
Сначала определимся с d. Несложно заметить, что всегда найдутся две точки квадрата, двигающиеся по параллельным, но не совпадающим прямым. В таком случае строна квадрата — это расстояние между прямыми, то есть одно из чисел |xi - xj| или |yi - yj|. Это и есть множество, в котором будет перебираться d.
Чтобы понять, где перебирать x и y, переберём d из построенного выше множества и рассмотрим два случая.
1. Есть две точки, которые двигаются по перпендикулярным прямым. Значит, в точке пересечения этих прямых есть вершина квадрата. Нижняя левая точка в каждой координате либо совпадает с ней, либо отличается на d. Точка пересечения прямых имеет координаты (xi, yj), значит, нижняя левая — (xi ± d, yj ± d) для некоторых i и j. Добавим все координаты xi, xi + d, xi - d в перебираемое множество.
2. Все точки двигаются по параллельным прямым. Будем считать, что по горизонтальным; случай вертикальных рассматривается аналогично. Снова переберём перестановку и сдвинем каждую точку так, чтобы после своего движения она совпала с нижней левой вершиной квадрата. Вторую точку надо сдвинуть на вектор ( - d, 0), третью — на (0,  - d), четвёртую — на ( - d,  - d). После этого четыре точки должны оказаться на одной прямой. Теперь задачу можно переформулировать так: есть четыре точки на прямой, нужно сдвинуть их в одну точку так, чтобы минимизировать максимальный сдвиг. Несложно видеть, что сдвигать нужно в середину полученного отрезка, то есть точку (maxX - minX) / 2 (из-за требования целочисленности ответа можно округлять в любую сторону). Перебрав все перестановки, получим ещё один набор, в котором надо перебирать координату первой точки требуемого квадрата.
За сколько это работает? Обозначим размеры соответствующих множеств за D и X. Тогда D = C42·2 = 12. Теперь для каждого d в первом случае генерируется 4·3 = 12 координат, во втором — не более чем 4! = 24. Итого X ≤ 12·(12 + 24) = 432. Основная часть решения работает за $$D \cdot X \cdot Y \cdot 4! \sim 5 \cdot 10^{7}$$; однако невозможно построить тест, на котором реализуются всевозможные конфигурации с движением по параллельным прямым, поэтому на самом деле перебирать придётся гораздо меньше.