虽然数学上满足距离公理玩意儿的都能被叫做距离，但竞赛中一般只用到曼哈顿距离、欧氏距离。然鹅这么简单的两种距离(不就是特殊的Lp距离)还是有点东西的。
曼哈顿距离
首先，平面绝对值和可以拆成四项取max。
\[|x_1 – x_2| + |y_1 – y_2| \\ = max\{(x_1-x_2)+(y_1-y_2),\cdots,\cdots,\cdots \} \\ = max\{(x_1+y_1)-(x_2+y_2),(x_1-y_1)+(x_2-y_2),\\ (-x_1+y_1)+(-x_2+y_2),(-x_1-y_1)-(-x_2-y_2)\}\]
这样，点对的最大曼哈顿距离就可以O(n)算了。
d维的空间也一样，二进制枚举符号，时间复杂度为O(n*2^d)。当然d太大的话过于暴力没有意义。
原题：http://poj.org/problem?id=2926
曼哈顿距离<->切比雪夫距离
切比雪夫距离是坐标差的最大值，即\(L^\infty\)范数。等距面为一个中心在原点的正方形。由于曼哈顿距离的等距面为顶点在轴上的正方形，所以两个距离是同构的，通过旋转可以互相转换。
曼哈顿转切比雪夫 \( (x, y) \rightarrow (x+y,x-y) \)
切比雪夫转曼哈顿 \( (x, y) \rightarrow (\frac{x+y}{2},\frac{x-y}{2}) \)
现在看前面的平面最远曼哈顿距离就更好理解了，就是转到切比雪夫距离上算一下最大的长和宽。
很多情况下，与曼哈顿距离有关的题目处理起来非常不方便，因为等距面与坐标轴不平行。这时候经常会把点之间的距离看成正斜线和反斜线的坐标之差，实际上就是切比雪夫距离。
例如，xdoj1064要算两个曼哈顿区域的并，需要转45度再算交 http://acm.xidian.edu.cn/problem.php?id=1064
三维空间中并不能直接旋转坐标得到变换，这是因为三维的曼哈顿等距面(正三轴形)是一个正八面体，与正六面体(aka 正方体)不同，至少需要四个坐标才能转换为切比雪夫距离。而数学上正八面体与正方体互为对偶。
同理四维空间中的正四轴形是一个正十六胞体，它与正八胞体(aka 超立方体)互为对偶。
点集曼哈顿最近点
问题：给定一个点集，多次询问点到点集的最小曼哈顿距离。
考虑离线，把所有点按x轴排序。分别计算询问点的第三象限和第四象限上的最近点。以离散化的y坐标为数组下标，上半区就用线段树/树状数组维护x-y的最小值，查询大于当前y的最小值。下半区同理。
复杂度O(nlogn)。
要求在线？查询时有两个限制条件。划分树。
要求带修？归并树/主席树/树套树。
平面最小曼哈顿生成树
朴素kruskal O(n^2 logn)，朴素Prim O(n^2)。显然n^2的连边中，大部分连边是没用的。有结论：每个点划分平面为八个部分，每个45°的范围内最多只可能连一条边，这样连边就降到O(n)了。于是用最近曼哈顿点的方法求出45°范围内的最近点。通过翻转操作，可以得到各个方向内的最近连边。
O(nlogn)。
欧几里得距离
平面全局最近点对
这是分治算法非常经典的应用。按x轴分治，递归算出左半平面和右半平面的最小距离d。那么跨区间的最近点对只可能出现在分治中心点[x-d, x+d]的区间内。这样的点对还比较多。但我们只要把这个区间内的点按y轴排序，枚举出每个点之后[y, y+d]范围内的点。可以证明这样的点不超过6个。
写起来就是在归并排序后面加个几行。
一个变形是平面最小周长三角形，因为过分治中心的边长度不会超过目前最小周长的一半，同样枚举即可。
平面最远点对
凸包+旋转卡壳即可。
平面最小生成树
一般用朴素的Prim O(n^2)已经差不多了，因为是完全图不需要堆优化。
同样会发现很多连边是浪费的。O(nlogn)算法需要Delaunay三角剖分，剖分后的边数是O(n)的。但是求Delaunay三角剖分过于神仙。
共性
有关距离的定义
一般距离要求有三角不等式，其中除了曼哈顿距离可能取到等号外，其他距离上三角不等式是严格的。
有时候三角不等式会有用。比如凸包上的TSP问题中，两条路线在平面上不可能交叉，所以可以排序后dp。
k-d树
之前的各种最小、最大距离，甚至是带动态修改的问题，都可以用k-d树做，但会慢一些。
k-d树建立把空间按维度顺序划分为几个子部分。查询的时候排除不必要的子空间来优化。查询的过程看起来更像是某种剪枝。k-d树虽然在低维度、随机数据上是log(n)的，但需要注意最坏情况下单次查询是\(O(n^(1-1/d))\)的。
动态修改问题中，k-d树会因为加入、删除变得不平衡，所以会用到替罪羊树的写法，出现不平衡后拍扁重建。
其他
四分树、八叉树这些很少在比赛中用到，因为很难保证维护的复杂度，当然现实应用中还是比较常用的。