← 返回题目列表

Codeforces · 1845/B

B. 一起来

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

鲍勃和卡罗尔和爱丽丝出去玩了一整天,但现在该回家了。 Alice、Bob 和 Carol 生活在一个无限的二维网格中,分别位于 $$$A$$$、$$$B$$$ 和 $$$C$$$ 单元格中。现在,它们都在单元格 $$$A$$$ 中。

如果鲍勃(或卡罗尔)在某个单元格中,他(她)可以移动到相邻单元格之一。如果两个单元共享一侧,则称为相邻单元。例如,单元格 $$$(3, 5)$$$ 有四个相邻单元格:$$$(2, 5)$$$、$$$(4, 5)$$$、$$$(3, 6)$$$ 和 $$$(3, 4)$$$。

Bob 想要返回单元格 $$$B$$$,Carol 想要返回单元格 $$$C$$$。他们都想走最短的路径,即。 e.沿着由尽可能少的单元组成的路径。但他们也想一起走。

如果鲍勃和卡罗尔各自使用最短路径之一步行回家,那么他们最多可以一起走多少个单元格?

输入

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

每个测试用例的第一行包含两个整数 $$$x_A$$$ 和 $$$y_A$$$ ($$$1 \le x_A, y_A \le 10^8$$$) - 单元格 $$$A$$$ 的位置,Bob 和 Carol 现在所在的位置。

第二行包含两个整数 $$$x_B$$$ 和 $$$y_B$$$ ($$$1 \le x_B, y_B \le 10^8$$$) — 单元格 $$$B$$$(鲍勃的房子)的位置。

第三行包含两个整数 $$$x_C$$$ 和 $$$y_C$$$ ($$$1 \le x_C, y_C \le 10^8$$$) - 单元格 $$$C$$$(卡罗尔的房子)的位置。

输入的附加约束:单元格 $$$A$$$、$$$B$$$ 和 $$$C$$$ 在每个测试用例中都是成对不同的。

输出

对于每个测试用例,打印单个整数 - 如果鲍勃和卡罗尔各自沿着最短路径之一回家,则鲍勃和卡罗尔可以一起行走的最大单元格数。

示例

输入 #1

3
3 1
1 3
6 4
5 2
2 2
7 2
1 1
4 3
5 5

输出 #1

3
1
6

注意

在所有图片中,红色表示仅属于 Bob 路径的单元格,浅蓝色表示仅属于 Carol 路径的单元格,深蓝色表示属于两条路径的单元格。

第一个测试用例的最佳路线之一如下所示:

第二个测试用例的最佳答案如下所示:

第三个测试用例的最佳答案之一如下所示: