#CODEFORCESP8715. Come Together.2B

    ID: 861 远端评测题 2000ms 256MiB 尝试: 10 已通过: 4 难度: 9 上传者: 标签>geometryimplementationmath*900translated小学组

Come Together.2B

Come Together

题面描述

给定无限大的网格图中 AABBCC 三点的横纵坐标,你需要求出,从 AA 分别到 BBCC 的最短路径最大有多少格点重合。

输入格式

第一行包含单个整数tt1t1041\le t\le 10^4)——测试用例的数量。 每个测试用例的第一行包含两个整数xAx_AyAy_A1xAyA1081\le x_A,y_A\le 10^8)——单元格AA的位置。 第二行包含两个整数xBx_ByBy_B1xByB1081\le x_B,y_B\le 10^8)——单元格BB的位置。 第三行包含两个整数xCx_CyCy_C1xCyC1081\le x_C,y_C\le 10^8)——单元格CC的位置。 对输入的附加约束:在每个测试用例中,单元格AABBCC是成对不同的。

输出格式

对于每个测试用例,打印一个整数——从 AA 分别到 BBCC 的最短路径最大重合格点的数量。

样例 #1

样例输入 #1

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

样例输出 #1

3
1
6

提示

在所有图片中,红色表示仅属于AABB的路径的单元格,浅蓝色表示仅属于AACC的路径的单元格;深蓝色表示同时属于两条路径的单元格。 第一个测试用例的最佳路径如下所示:

AABB的路线包含55单元格,AACC的路线--77单元格,他们将一起访问33单元格。

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

AABB的路线包含44单元格,AACC的路线是33单元格,他们一起只访问11单元格。

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

AABB的路线包含66单元格,AACC的路线包含99单元格,他们将一起访问66单元格。