103592: [Atcoder]ABC359 C - Tile Distance 2
Description
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 _ {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.
Output
问题描述
平面被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位整数的范围。