← 返回题目列表

Codeforces · 1455/E

E. 四点

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

$$$\mathit{XY}$$$ 网格上有四个不同的整数点 $$$p_1$$$、$$$p_2$$$、$$$p_3$$$ 和 $$$p_4$$$。

在一步中,您可以选择 $$$p_i$$$ 点之一,并将其​​向四个方向之一移动 1。换句话说,如果您选择了点 $$$p_i = (x, y)$$$,则可以将其移动到 $$$(x, y + 1)$$$、$$$(x, y - 1)$$$、$$$(x + 1, y)$$$ 或 $$$(x - 1, y)$$$。

您的目标是移动点,使它们形成一个边长平行于 $$$\mathit{OX}$$$ 和 $$$\mathit{OY}$$$ 轴的正方形(允许边长为 $$$0$$$ 的正方形)。

制作这样一个正方形至少需要多少步?

输入

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

每个测试用例由四行组成。每行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$0 \le x, y \le 10^9$$$) - 点 $$$p_i = (x, y)$$$ 之一的坐标。

一个测试用例中的所有点都不同。

输出

对于每个测试用例,打印单个整数 - 形成正方形的最小步骤数。

示例

输入 #1

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

输出 #1

8
7
5

注意

在第一个测试用例中,最佳解决方案之一如下所示:

在第二个测试用例中,最优解决方案之一如下所示:

在第三个测试用例中,最优解之一如下所示: