Four Points
Contest: Educational Codeforces Round 99 (Rated for Div. 2)
Difficulty rating: 2400
Tags: brute force, constructive algorithms, flows, geometry, greedy, implementation, math, ternary search

You are given four different integer points $$$p_1$$$, $$$p_2$$$, $$$p_3$$$ and $$$p_4$$$ on $$$\mathit{XY}$$$ grid.

In one step you can choose one of the points $$$p_i$$$ and move it in one of four directions by one. In other words, if you have chosen point $$$p_i = (x, y)$$$ you can move it to $$$(x, y + 1)$$$, $$$(x, y - 1)$$$, $$$(x + 1, y)$$$ or $$$(x - 1, y)$$$.

Your goal to move points in such a way that they will form a square with sides parallel to $$$\mathit{OX}$$$ and $$$\mathit{OY}$$$ axes (a square with side $$$0$$$ is allowed).

What is the minimum number of steps you need to make such a square?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of four lines. Each line contains two integers $$$x$$$ and $$$y$$$ ($$$0 \le x, y \le 10^9$$$) — coordinates of one of the points $$$p_i = (x, y)$$$.

All points are different in one test case.

Output format:
For each test case, print the single integer — the minimum number of steps to make a square.

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

Note:
In the first test case, one of the optimal solutions is shown below:

In the second test case, one of the optimal solutions is shown below:

In the third test case, one of the optimal solutions is shown below:

Example input:
3
0 2
4 2
2 0
2 4
1 0
2 0
4 0
6 0
1 6
2 2
2 5
4 1

Example output:
8
7
5

Editorial:
Let's discuss two approaches to this problem. Firstly, let's think that we choose not four destination points but four lines on which sides of the square lie. It's two vertical lines with coordinates $$$x_1$$$ and $$$x_2$$$ and two horizontal lines $$$y_1$$$ and $$$y_2$$$ (of course, $$$|x_1 - x_2| = |y_1 - y_2|$$$).
The first approach is to note that
• either both $$$x_1$$$ and $$$x_2$$$ coincide with some $$$(p_i.x)$$$-s and $$$y_1$$$ coincide with one of $$$(p_i.y)$$$
• or both $$$y_1$$$ and $$$y_2$$$ coincide with some $$$(p_i.y)$$$-s and $$$x_1$$$ coincide with one $$$(p_i.x)$$$.
The second approach is more clever and faster. Let's assign a role for each point $$$p_i$$$ — which vertex of the final square this $$$p_i$$$ will be: left-bottom, left-top, right-bottom or right-top. There will be $$$4!$$$ such assignments. For simplicity let's say that the left-bottom vertex is $$$a$$$, left-top is $$$b$$$, right-bottom is $$$c$$$ and right-top is $$$d$$$.
If we rewrite our total distance formulas, we can note that instead of summing the distance between points, we can sum the distance from lines to the points which should lie on it. In other words, we can calculate the answer as $$$$$$(|a_x - x_1| + |b_x - x_1|) + (|c_x - x_2| + |d_x - x_2|) + \\ + (|a_y - y_1| + |c_y - y_1|) + (|b_y - y_2| + |d_y - y_2|).$$$$$$
Let's look at the left side $$$x_1$$$. If $$$\min(a_x, b_x) \le x_1 \le \max(a_x, b_x)$$$ then the total distance is always $$$\max(a_x, b_x) - \min(a_x, b_x)$$$ and $$$x_1$$$ has it's optimal segment of values. Analogically, $$$x_2$$$ also has it's optimal segment of values $$$\min(c_x, d_x) \le x_2 \le \max(c_x, d_x)$$$.
Since we can choose $$$x_1$$$ as any value in its segment and $$$x_2$$$ as any value in its segment then the possible distance $$$|x_1 - x_2|$$$ (the side of the square) also forms a segment of possible values (let's name it as $$$[xSeg.l, xSeg.r]$$$) and can be calculated with pretty easy formula.
On the other hand, we can do the same with horizontal sides and compute the segment of optimal side length $$$[ySeg.l, ySeg.r]$$$ in the same manner.
Now, if $$$xSeg$$$ and $$$ySeg$$$ intersects then we can choose such side length $$$k$$$ that lies in both $$$xSeg$$$ and $$$ySeg$$$ and optimal for both vertical sides and horizontal sides.
Otherwise, without loss of generality, $$$xSeg.r < ySeg.l$$$ and if we choose $$$k = ySeg.l$$$ we need to pay extra "fee" since we out of $$$xSeg$$$ — it means that the chosen $$$k$$$ is greater than optimal $$$xSeg.r$$$, so we need to choose, for example, $$$x_1$$$ outside $$$[\min(a_x, b_x), \max(a_x, b_x)]$$$. And we need to pay $$$+2$$$ for each step outside of this segment.
In other words, the answer for a fixed permutation is $$$$$$(\max(a_x, b_x) - \min(a_x, b_x)) + (\max(c_x, d_x) - \min(c_x, d_x)) + \\ + (\max(a_x, c_x) - \min(a_x, c_x)) + (\max(b_x, d_x) - \min(b_x, d_x)) + \\ + 2 \cdot \max(0, \max(xSeg.l, ySeg.l) - \min(xSeg.r, ySeg.r)).$$$$$$