103592: [Atcoder]ABC359 C - Tile Distance 2

Problem Statement

The coordinate plane is covered with $2\times1$ tiles. The tiles are laid out according to the following rules:

• For an integer pair $(i,j)$, the square $A _ {x,y}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace$ is contained in one tile.
• When $i+j$ is even, $A _ {i,j}$ and $A _ {i + 1,j}$ are contained in the same tile.

Tiles include their boundaries, and no two different tiles share a positive area.

Near the origin, the tiles are laid out as follows:

Takahashi starts at the point $(S _ x+0.5,S _ y+0.5)$ on the coordinate plane.

He can repeat the following move as many times as he likes:

• Choose a direction (up, down, left, or right) and a positive integer $n$. Move $n$ units in that direction.

Each time he enters a tile, he pays a toll of $1$.

Find the minimum toll he must pay to reach the point $(T _ x+0.5,T _ y+0.5)$.

Constraints

• $0\leq S _ x\leq2\times10 ^ {16}$
• $0\leq S _ y\leq2\times10 ^ {16}$
• $0\leq T _ x\leq2\times10 ^ {16}$
• $0\leq T _ y\leq2\times10 ^ {16}$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$S _ x$ $S _ y$
$T _ x$ $T _ y$

Output

Print the minimum toll Takahashi must pay.

Sample Input 1

5 0
2 5

Sample Output 1

5

For example, Takahashi can pay a toll of $5$ by moving as follows:

• Move left by $1$. Pay a toll of $0$.
• Move up by $1$. Pay a toll of $1$.
• Move left by $1$. Pay a toll of $0$.
• Move up by $3$. Pay a toll of $3$.
• Move left by $1$. Pay a toll of $0$.
• Move up by $1$. Pay a toll of $1$.

It is impossible to reduce the toll to $4$ or less, so print 5.

Sample Input 2

3 1
4 1

Sample Output 2

0

There are cases where no toll needs to be paid.

Sample Input 3

2552608206527595 5411232866732612
771856005518028 7206210729152763

Sample Output 3

1794977862420151

Note that the value to be output may exceed the range of a $32$-bit integer.

问题描述

平面被2x1的瓷砖覆盖。瓷砖的布局遵循以下规则：

• 对于整数对$(i,j)$，正方形$A _ {x,y}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace$包含在一个瓷砖内。
• 当$i+j$为偶数时，$A _ {i,j}$和$A _ {i + 1,j}$包含在同一个瓷砖内。

瓷砖包括它们的边界，且没有两个不同的瓷砖共享正面积。

在原点附近，瓷砖的布局如下：

高桥从坐标平面上的点$(S _ x+0.5,S _ y+0.5)$开始。

他可以自由重复以下操作：

• 选择一个方向（上、下、左、右）和一个正整数$n$。向该方向移动$n$单位。

每次他进入一个瓷砖，他需要支付1元过路费。

找出他必须支付的最小过路费以到达点$(T _ x+0.5,T _ y+0.5)$。

限制条件

• $0\leq S _ x\leq2\times10 ^ {16}$
• $0\leq S _ y\leq2\times10 ^ {16}$
• $0\leq T _ x\leq2\times10 ^ {16}$
• $0\leq T _ y\leq2\times10 ^ {16}$
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

$S _ x$ $S _ y$
$T _ x$ $T _ y$

输出

打印高桥必须支付的最小过路费。

样例输入1

5 0
2 5

样例输出1

5

例如，高桥可以通过以下方式支付5元过路费：

• 向左移动1。支付过路费0元。
• 向上移动1。支付过路费1元。
• 向左移动1。支付过路费0元。
• 向上移动3。支付过路费3元。
• 向左移动1。支付过路费0元。
• 向上移动1。支付过路费1元。

无法将过路费降低到4元或以下，所以打印5。

样例输入2

3 1
4 1

样例输出2

0

存在无需支付过路费的情况。

样例输入3

2552608206527595 5411232866732612
771856005518028 7206210729152763

样例输出3

1794977862420151

注意输出的值可能超过32位整数的范围。