曼哈顿距离、切比雪夫距离

读大佬的博客 附上链接，，图也是人家的 对不起 QAQ

曼哈顿距离

曼哈顿距离：d(i,j)=|X1-X2|+|Y1-Y2|.
也就是横纵坐标差的绝对值的和。

切比雪夫距离

切比雪夫距离：二个点之间的距离定义是其各坐标数值差绝对值的最大值

一个是和、一个是最大值 。废话

曼哈顿距离的图
两者可以相互转换，

切比雪夫的图

很像？两者可以相互转换
原坐标系中的 曼哈顿距离转切尔雪夫：坐标：(x+y,x-y);
原坐标系中的 切比雪夫转曼哈顿：坐标：((x+y)/2,(x-y)/2);
两个式子互逆

换了之后 原图中的曼哈顿就等于现在图里的切比雪夫
有的题中 如果用曼哈顿比较麻烦 就可以换成切比雪夫
反之也可以

例题：牛客挑战赛34 - D 拉普兰德的愿望

题目大意：
给出n个坐标让求曼哈顿距离>=d的个数就是总的小于d的

然后 用曼哈顿距离怎么做？ 不会 好难好难 想了一下午 还很垃圾的想了一个错的，好明显的错误。。。 还给大佬讲了错的。。 尴尬
然后 看了题解
题解：
曼哈顿距离转化为切比雪夫距离 然后只用计算如上图的 以当前点为中心边长为2d的正方形中有多少点 就是 离这个点距离小于d的点的个数 记得不算边界上的 因为题上要求大于等于d的 减去的应该是小于d的

用树状数组存y为i的个数 然后 枚举每个点 每个点只记 正方形的左半部分、枚举的时候顺便把x不符合的删了 y的话在树状数组里 就 前缀和 r的-l的。
哇 机智啊

代码：

```cpp
#include 
#include 
using namespace std;
const int maxn = 1e5+5;
struct Node
{int x,y;bool operator < (const Node & a

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！