题解：AT_abc359_c [ABC359C] Tile Distance 2
I_Love_DS
2024-06-25 14:09:53
## 前言
第一眼看到题面的图：不难啊，bfs 一下不就好了？
而看到数据范围的我：$0 \le sx,sy,tx,ty \le 10^{16}$ 哦。。。
## 思路
贪心。
本文题解里：
> $x$ 或 $y$ 轴距离 为 两个点的 $x$ 或 $y$ 坐标的绝对值。
设答案为 $ans$。
1. 先竖着走完起点和终点的 $y$ 轴距离。此时，$ans \gets |ty - sy|$。
2. 为了之后方便，我们使 $sx$ 和 $tx$ 变成**他们所在的长方形中左面正方形的左下角坐标**。
3. 继上面的操作，我们设 $k = |sx - tx| - |sy - ty|$，其实就是从起始点走完起点和终点的 $y$ 轴距离的所在地点离终点的 $x$ 轴距离。（可借助[这位大佬的题解](https://www.luogu.com.cn/article/xtl9ppbo)的图理解一下）
4. 继上面的操作，如果 $k \le 0$，那么说明不用再花费额外的消费。否则每走 $2$ 个 $x$ 轴距离就要多消费 $1$，所以 $ans \gets ans + k \div 2$。
完结，撒花！
## 代码
注意一下 `long long` 就行。
```cpp
#include <bits/stdc++.h>
using namespace std;
long long sx, sy, ex, ey;
int main() {
scanf("%lld%lld%lld%lld", &sx, &sy, &ex, &ey);
long long ans = abs(ey - sy);
//1
if (sy % 2 == 0) sx -= abs(sx % 2);
else sx -= abs((sx + 1) % 2);
if (ey % 2 == 0) ex -= abs(ex % 2);
else ex -= abs((ex + 1) % 2);
//2
long long k = (abs(ex - sx) - abs(ey - sy));
//3
ans += max(0LL, k / 2); //防止 k<=0
//4
printf("%lld", ans);
return 0;
}
```