简介
大概就是二维空间中的几种距离之间的关系吧
曼哈顿距离
平面中 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的曼哈顿距离为 $|x_1-x_2|+|y_1-y_2|$
四连通的图中两点的距离为曼哈顿距离
切比雪夫距离
平面中 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的切比雪夫距离为 $max\lbrace |x_1-x_2|,|y_1-y_2|\rbrace$
八连通的图中两点的距离为切比雪夫距离
曼哈顿距离和切比雪夫距离之间的转换
- 四连通转八连通：$(x,y)\rightarrow (x+y,x-y)$
- 八连通转四连通：$(x,y)\rightarrow (\frac{x+y}{2},\frac{x-y}{2})$
为什么转换
在求一个点到其它点的距离和的时候，曼哈顿距离可以两个坐标分开来考虑
更进一步，对于 $n$ 个点的四连通图，如果选取一个点 $x$ 使得 $x$ 到其它所有点的距离和最小
则 $x$ 的横坐标是原图中所有点的横坐标的中位数，纵坐标是原图中所有点的纵坐标的中位数
在求选一个点到其他点的距离最大值最小时，切比雪夫距离可以两个坐标分开来考虑
更进一步，我们令 $mxx$ 为所有点的横坐标的最大值，$mnx$ 为所有点的横坐标的最小值，$mxy$ 和 $mny$ 同理
则我们应该选 $(\frac{mnx+mxx}{2},\frac{mny+mxy}{2})$，问题就是我们要确定在整数坐标的情况下是否能变回去
所以我们不能只在四连通的方向上抖动，而应该在下取整之后在 $[-1,2]$ 的范围抖动
例题
简要题意：给定 $n$ 个在 $k$ 维空间的整点 $a_i$，两点的距离为 $k$ 维空间的曼哈顿距离，即 $\sum_{i=1}^k|a_{x,i}-a_{y,i}|$，现在有 $m$ 次操作，操作由两种：给定 $x$ 和一个新的坐标 $b$，令 $a_x=b$；给定区间 $[l,r]$，求区间 $[l,r]$ 内距离最远的两个点的距离
$n,m\le 2\times 10^5, k\le 5$，时间限制 $6$ 秒
简要题解：我们考虑将曼哈顿距离的绝对值拆出来
由于答案只需要求最大值，我们直接枚举每个数的符号，注意到只有满足正确符号的两个距离才有可能凑成最大值
所以我们直接那线段树维护 $2^k$ 个状态的最大值即可
时间复杂度 $O(2^kn\log n)$
简要题意：给定 $n$ 个八连通二维平面上的点 $(x_i,y_i)$，求选一个给定点 $(x_i,y_i)$ 作为集合点，使得其它所有给定点到它的距离和最小
$n\le 10^5$
简要题解：切比雪夫距离计算距离和很不方便，我们转换成曼哈顿距离将两维分开
最后将答案除 $2$ 即可，注意到答案一定是偶数
简要题意：给定 $n$ 八连通二维平面上的点 $(x_i,y_i)$，求选择一个整点 $(x,y)$（可以不是给定点），使得所有给定点到它的距离和最小，求选择的方案数和最小的距离和
$n\le 10^5$
简要题解：首先现将切比雪夫距离转成曼哈顿距离
然后我们取中位数，如果 $n$ 是奇数，那么中位数唯一
由于整数坐标的限制，我们不能直接除 $2$
这个时候我们要抖动一下防止变回去的时候出现小数
如果 $n$ 是偶数，那么我们就统计一下矩形中有多少点两维坐标的奇偶性相同
简要题意：给定 $n$ 个点和 $m$ 个特殊位置，两点之间的距离为曼哈顿距离
要求新建一个特殊位置，使得所有点到最近的特殊位置的最大值最小
$n,m\le 10^5$
简要题解：首先用树状数组在四个方向上计算出每个点距离最近的特殊位置
然后二分答案，判断的时候将图转为八连通，这样利用切比雪夫距离可以将两个维度分开来判断
更进一步，我们令 $mxx$ 为所有点的横坐标的最大值，$mnx$ 为所有点的横坐标的最小值，$mxy$ 和 $mny$ 同理
则我们应该选 $(\frac{mnx+mxx}{2},\frac{mny+mxy}{2})$，问题就是我们要确定在整数坐标的情况下是否能变回去
我们不能只在四连通的方向上抖动，而应该在下取整之后在 $[-1,2]$ 的范围抖动