310516: CF1845B. Come Together
Description
Bob and Carol hanged out with Alice the whole day, but now it's time to go home. Alice, Bob and Carol live on an infinite 2D grid in cells $A$, $B$, and $C$ respectively. Right now, all of them are in cell $A$.
If Bob (or Carol) is in some cell, he (she) can move to one of the neighboring cells. Two cells are called neighboring if they share a side. For example, the cell $(3, 5)$ has four neighboring cells: $(2, 5)$, $(4, 5)$, $(3, 6)$ and $(3, 4)$.
Bob wants to return to the cell $B$, Carol — to the cell $C$. Both of them want to go along the shortest path, i. e. along the path that consists of the minimum possible number of cells. But they would like to walk together as well.
What is the maximum possible number of cells that Bob and Carol can walk together if each of them walks home using one of the shortest paths?
InputThe first line contains the single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains two integers $x_A$ and $y_A$ ($1 \le x_A, y_A \le 10^8$) — the position of cell $A$, where both Bob and Carol are right now.
The second line contains two integers $x_B$ and $y_B$ ($1 \le x_B, y_B \le 10^8$) — the position of cell $B$ (Bob's house).
The third line contains two integers $x_C$ and $y_C$ ($1 \le x_C, y_C \le 10^8$) — the position of cell $C$ (Carol's house).
Additional constraint on the input: the cells $A$, $B$, and $C$ are pairwise distinct in each test case.
OutputFor each test case, print the single integer — the maximum number of cells Bob and Carol can walk together if each of them goes home along one of the shortest paths.
ExampleInput3 3 1 1 3 6 4 5 2 2 2 7 2 1 1 4 3 5 5Output
3 1 6Note
In all pictures, red color denotes cells belonging only to Bob's path, light blue color — cells belonging only to Carol's path, and dark blue color — cells belonging to both paths.
One of the optimal routes for the first test case is shown below:
The optimal answer for the second test case is shown below:
One of the optimal answers for the third test case is shown below:
Input
题意翻译
给定无限大的网格图中 $A$，$B$，$C$ 三点的横纵坐标，你需要求出，从 $A$ 分别到 $B$ 与 $C$ 的最短路径最大有多少格点重合。Output
Bob和Carol在Alice家玩了一整天，现在需要各自回家。他们住在无限大的二维网格上，分别位于单元格A、B和C。目前，他们都在单元格A中。Bob（或Carol）可以在某个单元格中移动到其相邻的单元格。如果两个单元格共享一条边，则称它们为相邻的。例如，单元格(3, 5)有四个相邻单元格：(2, 5)、(4, 5)、(3, 6)和(3, 4)。Bob想回到单元格B，Carol想回到单元格C。他们都希望沿着最短路径走，即包含最少单元格数的路径。但他们也希望能一起走。
问：如果他们各自沿着最短路径回家，Bob和Carol能一起走过的最大单元格数是多少？
输入输出数据格式：
输入：
- 第一行包含单个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的第一行包含两个整数x_A和y_A（1≤x_A, y_A≤10^8）——单元格A的位置，Bob和Carol现在都在这里。
- 第二行包含两个整数x_B和y_B（1≤x_B, y_B≤10^8）——单元格B（Bob的家）的位置。
- 第三行包含两个整数x_C和y_C（1≤x_C, y_C≤10^8）——单元格C（Carol的家）的位置。
- 输入的附加限制：在每一个测试用例中，单元格A、B和C两两不同。
输出：
- 对于每个测试用例，打印一个整数——如果Bob和Carol各自沿着最短路径回家，他们能一起走过的最大单元格数。
示例：
输入：
```
3
3 1
1 3
6 4
5 2
2 2
7 2
1 1
4 3
5 5
```
输出：
```
3
1
6
```题目大意： Bob和Carol在Alice家玩了一整天，现在需要各自回家。他们住在无限大的二维网格上，分别位于单元格A、B和C。目前，他们都在单元格A中。Bob（或Carol）可以在某个单元格中移动到其相邻的单元格。如果两个单元格共享一条边，则称它们为相邻的。例如，单元格(3, 5)有四个相邻单元格：(2, 5)、(4, 5)、(3, 6)和(3, 4)。Bob想回到单元格B，Carol想回到单元格C。他们都希望沿着最短路径走，即包含最少单元格数的路径。但他们也希望能一起走。 问：如果他们各自沿着最短路径回家，Bob和Carol能一起走过的最大单元格数是多少？ 输入输出数据格式： 输入： - 第一行包含单个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例的第一行包含两个整数x_A和y_A（1≤x_A, y_A≤10^8）——单元格A的位置，Bob和Carol现在都在这里。 - 第二行包含两个整数x_B和y_B（1≤x_B, y_B≤10^8）——单元格B（Bob的家）的位置。 - 第三行包含两个整数x_C和y_C（1≤x_C, y_C≤10^8）——单元格C（Carol的家）的位置。 - 输入的附加限制：在每一个测试用例中，单元格A、B和C两两不同。 输出： - 对于每个测试用例，打印一个整数——如果Bob和Carol各自沿着最短路径回家，他们能一起走过的最大单元格数。 示例： 输入： ``` 3 3 1 1 3 6 4 5 2 2 2 7 2 1 1 4 3 5 5 ``` 输出： ``` 3 1 6 ```