201093: [AtCoder]ARC109 D - L

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

We have three stones at points $(0, 0)$, $(1,0)$, and $(0,1)$ on a two-dimensional plane.

These three stones are said to form an L when they satisfy the following conditions:

  • Each of the stones is at integer coordinates.
  • Each of the stones is adjacent to another stone. (That is, for each stone, there is another stone whose distance from that stone is $1$.)
  • The three stones do not lie on the same line.

Particularly, the initial arrangement of the stone - $(0, 0)$, $(1,0)$, and $(0,1)$ - forms an L.

You can do the following operation any number of times: choose one of the stones and move it to any position. However, after each operation, the stones must form an L. You want to do as few operations as possible to put stones at points $(ax, ay)$, $(bx, by)$, and $(cx, cy)$. How many operations do you need to do this?

It is guaranteed that the desired arrangement of stones - $(ax, ay)$, $(bx, by)$, and $(cx, cy)$ - forms an L. Under this condition, it is always possible to achieve the objective with a finite number of operations.

You will be given $T$ cases of this problem. Solve each of them.

Notes

We assume that the three stones are indistinguishable. For example, the stone that is initially at point $(0,0)$ may be at any of the points $(ax, ay)$, $(bx, by)$, and $(cx, cy)$ in the end.

Constraints

  • $1 \leq T \leq 10^3$
  • $|ax|,|ay|,|bx|,|by|,|cx|,|cy| \leq 10^9$
  • The desired arrangement of stones - $(ax, ay)$, $(bx, by)$, and $(cx, cy)$ - forms an L.

Input

Input is given from Standard Input in the following format:

$T$
$\text{case}_1$
$\vdots$
$\text{case}_T$

Each case is in the following format:

$ax$ $ay$ $bx$ $by$ $cx$ $cy$

Output

Print $T$ values. The $i$-th value should be the minimum number of operations for $\text{case}_i$.


Sample Input 1

1
3 2 2 2 2 1

Sample Output 1

4

Let us use # to represent a stone. You can move the stones to the specified positions with four operations, as follows:

....    ....    ....    ..#.    ..##
#... -> ##.. -> .##. -> .##. -> ..#.
##..    .#..    .#..    ....    ....

Sample Input 2

10
0 0 1 0 0 1
1 0 0 1 1 1
2 -1 1 -1 1 0
1 -2 2 -1 1 -1
-1 2 0 2 -1 3
-1 -2 -2 -2 -2 -3
-2 4 -3 3 -2 3
3 1 4 2 4 1
-4 2 -4 3 -3 3
5 4 5 3 4 4

Sample Output 2

0
1
2
3
4
5
6
7
8
9

Input

题意翻译

二维直角坐标系上,初始在 $(0,0),(1,0),(0,1)$ 三个位置各有一个石子。 定义三个石子符合 L 形当且仅当: - 三个石子所在位置坐标都是整数 - 三个石子都相邻(也就是对每个石子都存在一个石子与它距离为 $1$) - 三个石子不在同一直线上 你可以进行若干次操作,每次操作移动任意一个石子,但要求每次移动后三个石子依旧符合 L 形。 $T$ 次询问,每次询问给定坐标 $(ax,ay),(bx,by),(cx,cy)$,求从初始位置将石子移动到这三个位置的最小操作次数。 每次询问独立。 数据范围与保证: - $1\le T\le 10^3$ - $|ax|,|ay|,|bx|,|by|,|cx|,|cy|\le 10^9$ - 每次输入的三个坐标符合 L 形。

加入题单

上一题 下一题 算法标签: