AT_abc359_c [ABC359C] Tile Distance 2

题目描述

在坐标平面上铺满了 $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$ 包含在某一块瓷砖中。
• 当 $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)$ 所需支付的最小通行费。

输入格式

输入通过标准输入按以下格式给出。

$S_x$ $S_y$ $T_x$ $T_y$

输出格式

输出高桥君需要支付的最小通行费。

输入输出样例 #1

输入 #1

5 0
2 5

输出 #1

5

输入输出样例 #2

输入 #2

3 1
4 1

输出 #2

0

输入输出样例 #3

输入 #3

2552608206527595 5411232866732612
771856005518028 7206210729152763

输出 #3

1794977862420151

说明/提示

限制条件

• $0\leq S_x\leq 2\times 10^{16}$
• $0\leq S_y\leq 2\times 10^{16}$
• $0\leq T_x\leq 2\times 10^{16}$
• $0\leq T_y\leq 2\times 10^{16}$
• 输入均为整数

样例解释 1

例如，可以如下移动使得支付的通行费为 $5$。

• 向左移动 $1$，通行费 $0$。
• 向上移动 $1$，通行费 $1$。
• 向左移动 $1$，通行费 $0$。
• 向上移动 $3$，通行费 $3$。
• 向左移动 $1$，通行费 $0$。
• 向上移动 $1$，通行费 $1$。

无法将通行费减少到 $4$ 或更少，因此请输出 5。

样例解释 2

有时也可以不支付任何通行费。

样例解释 3

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

由 ChatGPT 4.1 翻译