/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
座標平面上に 2\times1 の大きさのタイルが敷き詰められています。 タイルは、次の規則に従って敷き詰められています。
- 整数の組 (i,j) に対し、正方形 A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace は 1 つのタイルに含まれる。
- i+j が偶数のとき、A _ {i,j} と A _ {i + 1,j} は同じタイルに含まれる。
ただし、タイルは境界を含むものとし、共通部分が正の面積をもつような 2 つの異なるタイルは存在しないとします。
原点の近くでは、タイルは以下のように敷き詰められています。
高橋君は、はじめ座標平面上の点 (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\operatorname{bit} 整数の範囲に収まらない場合があることに注意してください。
Score : 350 points
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 _ {i,j}=\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.