二维曼哈顿和切比雪夫距离转换的简要(乱搞)证明

2018-03-15jzqjzq?

文章目录

当然这个东西有更好的解释方法。。。这里纯属娱乐233
说正事之前,先定义一些东西
定义$a(x1,y1),b(x2,y2) (x1<=x2,y1<=y2)$(这样方便证明,其他情况是一样的),$dist(a,b)$表示i,j两点的曼哈顿距离

注意:这不是在推出来两者的关系QAQ
因为如果直接写的话我会证成什么样子都不知道QAQ
刚做一题切比雪夫转曼哈顿的神(其实是丝薄)题,顿时有感而发,想证明一下这个东西:
$$max(|x2-x1|,|y2-y1|)=dist((\frac{x2+y2}{2},\frac{x2-y2}{2}),(\frac{x1+y1}{2},\frac{x1-y1}{2}))$$
等号左边就是切比雪夫距离(就是横纵坐标之差的较大值)
现在我们来证明这个结论!
我们把右边化开来:
$$dist((\frac{x2+y2}{2},\frac{x2-y2}{2}),(\frac{x1+y1}{2},\frac{x1-y1}{2}))$$
$$=|\frac{(x2+y2)-(x1+y1)}{2}|+|\frac{((x2-y2)-(x1-y1)}{2}|$$
$$=\frac{|(x2+y2)-(x1+y1)|+|(x2-y2)-(x1-y1)|}{2}$$
$$=\frac{|(x2-x1)+(y2-y1)|+|(x2-x1)-(y2-y1)|}{2}$$
接下来开始分类讨论
如果$x2-x1>y2-y1$:
$$=\frac{x2-x1+y2-y1+x2-x1-y2+y1}{2}=x2-x1$$
如果$x2-x1<y2-y1$:
$$=\frac{x2-x1+y2-y1+y2-y1-x2+x1}{2}=y2-y1$$
如果等于呢?那就是两个都可以了啊
当然这里拿了一个特殊例子来证,其实所有情况都是一样的(就是拿绝对值符号的问题QAQ)
这样呢就可以解决一些神奇的切比雪夫距离的问题了
比如这个:Luogu3964
把切比雪夫转成曼哈顿然后直接前缀和一波……
就是这样啊