企业官网建设流程全解析

每日一题系列更新到第17期。这一期的标题看着像是几何题，实际上考的是坐标系移动和切比雪夫距离（Chebyshev distance）的配合。题目背景很接地气：平面上有n个点，要选一个中心位置，让所有点到这个中心位置的曼哈顿距离最大值尽量小。第一眼看到这个问题，我脑子里跳出来的是“分别对x、y取中位数”，结果样例直接挂了。后来把坐标系整体旋转45度，用(x+y, x-y)这组新坐标重新看问题，曼哈顿距离会变成新坐标系下的切比雪夫距离，最大值最小问题瞬间变成“用一个边与坐标轴平行的正方形盖住所有点”。这篇文章会把推导过程、证明、完整代码和调试经验一次讲透，适合被坐标变换题坑过的同学，也适合准备面试或算法竞赛但还没系统整理L1、L∞互换技巧的人。

1. 把题目翻译成人话：仓库选址和方形世界

1.1 题目输入输出长什么样

题面可以这样描述：给定n个平面点，坐标都是整数，例如(0,0), (1,1), (2,0)。现在要找一个中心点(cx, cy)，使得所有点到它的曼哈顿距离|x-cx| + |y-cy|的最大值最小。输出这个最小的最大距离，以及任意一个能达到最优值的中心点坐标。

这个模型在现实里非常常见。比如要在城区里建一个应急物资仓库，配送员只能沿着横竖街道走，也就是只能走曼哈顿路线，那么“最远的配送员跑多远”就是上面那个最大值。我们希望这个最远距离尽可能小，也就是要优化最坏情况。另一个例子是外卖平台的取餐点选址，骑手从不同方向过来，路程按街区计算，同样适用。

这类问题很容易让人误以为“把x排序取中位数、y排序取中位数”就行，因为求曼哈顿距离之和最小确实可以这样干。但题目要的是最大值最小，不是总和最小。目标函数从求和变成取max之后，中位数的位置就不对了。拿例子来说，点(0,0), (1,1), (2,0)，x的中位数是1，y的中位数是1，中心(1,1)到三个点的曼哈顿距离分别是2、0、2，最大值是2。但如果你选中心(1,0)，距离分别是1、1、1，最大值是1，明显更优。这说明问题没那么简单，需要用几何结构重新理解。

1.2 第一个朴素方案为什么会挂

在继续推导之前，我想先把这个误区讲透，因为这是很多人第一次写代码时踩的坑。求曼哈顿距离总和最小，本质上每个点是独立的，中位数能均衡两侧的数量；但求最大值最小，比较的是“最远的那个点”，中位数无法控制最远点的距离。一维的例子最直观：数轴上三个点1、2、100。中位数是2，最远距离是max(2-1, 100-2)=98；你去取均值51.5，最远距离是max(51.5-1, 100-51.5)=50.5。虽然均值不是整数，但在这个问题里它比中位数好得多。二维情况下，两个维度的“最优中心”可以分别取中点区间，而不是取中位数。

这个例子也说明了一个关键点：最大值最小问题通常和“区间跨度”有关，一个维度的最优取值往往落在最小值和最大值的中点附近。换个角度看，要覆盖住一维数轴上所有点，半径最小只能是跨度的一半；中心点取中点。二维曼哈顿场景虽然不能直接拆成两个独立的一维问题，但只要换一个坐标系，它就能拆开，这就是切比雪夫距离登场的地方。

1.3 先建立直觉：曼哈顿距离对应的方形世界

曼哈顿距离的“单位圆”是一个旋转45度的正方形，顶点在坐标轴上。切比雪夫距离的“单位圆”则是边与坐标轴平行的正方形。两者之间就差了一个旋转，或者严格说，差一个45度的旋转加缩放。

切比雪夫距离有一个特别生活化的名字叫“棋盘距离”。想象国际象棋里的国王，它一步可以朝八个方向走一格。从(x1,y1)走到(x2,y2)，国王需要的最少步数就是max(|dx|, |dy|)。原因是国王每步横、竖、斜都能走，水平差和竖直差中较大的那个决定步数。这个度量的几何意义非常清楚：离原点切比雪夫距离不超过R的点，正好围成一个边长为2R、边与坐标轴平行的正方形。所以“切比雪夫距离最小覆盖问题”本质上就是“找一个轴对齐的正方形盖住所有点”。

这些直觉建立起来之后，再回头看仓库选址问题：曼哈顿距离的最坏情况优化，能不能也变成一个“用方形去覆盖点”的问题？答案是能，做法就是把坐标系移动一下，换成一组斜45度的坐标轴。下一节把公式推导完整写出来。

2. 切比雪夫距离的几何直觉与公式基础

2.1 切比雪夫距离的数学定义

切比雪夫距离的定义式是d∞(A,B) = max(|xA-xB|, |yA-yB|)。它和欧氏距离、曼哈顿距离并列，是Lp距离族里p趋于无穷大的情况。之所以单独写一题来讲，是因为它有一个很特别的几何性质：它的等距线是正方形，而且正方形的边和坐标轴平行。

在很多算法题里，切比雪夫距离经常以“国王走棋盘”“最大边差值”的形式出现。处理它的时候，最常见的手段不是直接计算，而是把坐标做伸缩。因为max(|dx|,|dy|)里带一个max，没法直接拆成两个独立项；但如果把坐标轴旋转45度，max就会被“打开”成两个绝对值的和，这就是曼哈顿距离。反过来说，曼哈顿距离里带一个加号，不好分别处理两个方向，但换到新坐标系后，加号会变成max。

理解了这一点，就明白为什么那么多题解里会出现“把点变成(x+y, x-y)”这个操作了。它不是魔法，只是换了一把尺子。同一组点，换了坐标系之后，距离表达式变简单了，覆盖关系也变得更直观。这里说的“坐标系移动”，不单单指平移，还包括旋转和缩放。

2.2 旋转45度的坐标系移动到底在做什么

想象一张透明的坐标网格纸。你把它以原点为中心旋转45度，再按比例缩小，原来的横平竖直街道就变成了斜向街道。点还是那些点，物理位置没变，但它们在网格纸上的读数变了。这才是“坐标系移动”的本质：不是移动物体，而是换个角度看。

具体到公式，给定原始坐标(x,y)，定义新坐标：

u = x + y

v = x - y

这个变换的几何效果是：把原坐标轴旋转45度，并且整体放大了sqrt(2)倍。两个点之间的曼哈顿距离|dx|+|dy|，在新的(u,v)坐标系里恰好等于切比雪夫距离。这个恒等式是这套解法的地基，值得亲手推一遍。

用分类讨论证明很简单。设a=dx,b=dy。如果a和b同号，那么|a+b| = |a|+|b|，而|a-b| <= |a|+|b|，所以max(|a+b|, |a-b|) = |a|+|b|。如果a和b异号，那么|a-b| = |a|+|b|，而|a+b| <= |a|+|b|，结果一样。因此：

|dx| + |dy| = max(|dx+dy|, |dx-dy|)

这就证明了一个点P到候选中心C的曼哈顿距离，等于变换后两点在(u,v)坐标下的切比雪夫距离。

2.3 两个方向的转换公式表

这个变换不是单向的，反过来也能用。如果题目给的是切比雪夫距离，想把它转成曼哈顿距离，可以用类似方式定义u=(x+y)/2,v=(x-y)/2。因为缩放比例会影响数值，我把两组常用转换整理成表格：

第一行是这一题的核心。第二行也有用，比如有些题给的是切比雪夫距离，但需要套曼哈顿距离才会算的二维前缀和。两张表不需要硬背，记住一个原则：曼哈顿的“绝对值之和”对应新坐标系里的“绝对值最大项”，切比雪夫的“最大值”对应新坐标系里的“绝对值之和”。这个关系就像把不等式里的max和加法互换。

3. 核心变换：从最大曼哈顿距离到最小方形覆盖

3.1 把目标函数改写成切比雪夫形式

现在把原题的目标函数完整写一遍。设所有点为(xi, yi)，候选中心为(cx, cy)，目标函数是：

F = max_i ( |xi-cx| + |yi-cy| )

用上面证明的恒等式，对每个点有：

|xi-cx| + |yi-cy| = max( |(xi+yi)-(cx+cy)|, |(xi-yi)-(cx-cy)| )

定义：

ui = xi + yi

vi = xi - yi

cu = cx + cy

cv = cx - cy

于是原目标函数变成：

F = max( max_i |ui-cu|, max_i |vi-cv| )

这一步非常关键，因为它把一个二维耦合问题拆成了两个独立的一维投影问题。原坐标系下的曼哈顿距离是两个分量相加，x方向的偏差和y方向的偏差会互相影响；但在新的(u,v)坐标系下，切比雪夫距离只看每个维度各自的偏差取最大值，两个坐标轴彻底解耦。

3.2 为什么变换后问题会独立成两个维度

切比雪夫距离有一个让人舒服的性质：max_i max(|du_i|, |dv_i|)等于max( max_i |du_i|, max_i |dv_i| )。也就是说，“先对每个点看两个方向谁更大，再对所有点取最大”，等价于“先按u方向对所有点取最大，再按v方向对所有点取最大，最后比较”。交换了max的嵌套顺序，代价没有变。

换一个更直观的说法：在(u,v)坐标系里，要找的其实是“最小半径R的轴对齐正方形，能覆盖所有变换后的点”。这个正方形的u方向只需要考虑所有点u坐标的跨度，v方向只需要考虑所有点v坐标的跨度。两个方向互不干扰，可以单独算最优半径，再取较大者作为整体半径。

这正是“最小方形覆盖”问题的标准形态。切比雪夫距离的单位圆是轴对齐正方形，所以“最大化距离最小化”在这里转化成“要盖住所有点，正方形半边长最少是多少”。这个几何图像一旦建立，答案几乎可以一眼看出来。

3.3 最优中心与半径怎么取

单独看u方向。假设一堆点的u坐标最小值是minU，最大值是maxU。为了覆盖这两个端点，中心cu到其中任意一个的最远距离至少是(maxU - minU)/2。取cu = (minU + maxU)/2时，所有点的u方向偏差都不超过这个值，所以这一维的最优半径是：

Ru = (maxU - minU) / 2

v方向同理：

Rv = (maxV - minV) / 2

全局最小最大距离就是两者中较大的：

answer = max(Ru, Rv) = max(maxU-minU, maxV-minV) / 2

为什么这里可以用中点而不是中位数？因为问题是最大值最小，不是总和最小。中位数均衡的是点的数量，无法保证“离中心最远的点”不会太远；而中点直接压住了跨度。拿一维点[1,2,100]说，中位数中心2对应的最大距离是98，中点中心51.5对应的最大距离只有48.5。只要允许中心是实数，中点就是最优解。

这里有一点值得注意：最优中心的cu不一定要取唯一值。只要cu落在[minU, maxU]的中点附近，并且v方向也满足类似条件，整体半径都能达到最优。具体实现时取中点最省事，反变换也最对称。

3.4 反变换回原坐标系

题目要的是原坐标系里的中心点(cx, cy)，而我们的最优解算出来的是(cu, cv)。反变换公式直接从定义解出来：

cx = (cu + cv) / 2

cy = (cu - cv) / 2

用样例(0,0), (1,1), (2,0)走一遍。三个点的u分别是0、2、2，v分别是0、0、2。于是minU=0，maxU=2，minV=0，maxV=2。最优半径是max(2,2)/2=1。中心cu=1,cv=1，反变换得到cx=1,cy=0，正好是前面手动找出的最优中心(1,0)。

原坐标下中心点可能出现小数，比如1.5，这是允许的。如果题目强制中心必须是整数格点，那么答案要上取整，中心可以在中点附近枚举几个整数点取最优。这个细节我在第四节会专门展开。

4. 完整代码、调试样例与常见错误速查

4.1 可直接跑的Python实现

整套算法的代码非常短，核心只有几行。时间复杂度是O(n)，空间O(1)，对所有点的u、v分别维护最小值和最大值即可：

def solve(points): min_u = min_v = float("inf") max_u = max_v = float("-inf") for x, y in points: u = x + y v = x - y if u < min_u: min_u = u if u > max_u: max_u = u if v < min_v: min_v = v if v > max_v: max_v = v # 半径：新坐标系下切比雪夫距离的一半跨度 ans = max(max_u - min_u, max_v - min_v) / 2.0 # 新坐标系下的最优中心 cu = (min_u + max_u) / 2.0 cv = (min_v + max_v) / 2.0 # 反变换回原坐标 cx = (cu + cv) / 2.0 cy = (cu - cv) / 2.0 return ans, (cx, cy)

调用方式很简单：

pts = [(0, 0), (1, 1), (2, 0)] ans, center = solve(pts) print(ans, center) # 1.0 (1.0, 0.0)

这里需要注意，u和v都可能超过原始坐标的范围，比如坐标在1e9量级时，u、v会到2e9。用Python不用担心溢出，但用C++时一定要开long long，否则跨度计算会直接爆掉。这个坑我在竞赛里见过不少次。

4.2 用暴力对拍验证正确性

写完正解之后，我习惯写一个暴力版本做随机对拍，尤其是这种带坐标变换的题目，容易在某一步把公式记翻。暴力做法是枚举候选中心，检查所有点到它的曼哈顿距离最大值。因为中心可以是任意实数，实际对拍时把中心限制在整数格点上，再配合随机小数据，就足够发现公式错误了。

import random def brute(points): xs = [p[0] for p in points] ys = [p[1] for p in points] best = float("inf") best_center = None for cx in range(min(xs) - 1, max(xs) + 2): for cy in range(min(ys) - 1, max(ys) + 2): cur = max(abs(x - cx) + abs(y - cy) for x, y in points) if cur < best: best = cur best_center = (cx, cy) return best, best_center for _ in range(10000): n = random.randint(1, 8) pts = [(random.randint(-5, 5), random.randint(-5, 5)) for _ in range(n)] ans1, _ = solve(pts) ans2, _ = brute(pts) if abs(ans1 - ans2) > 0.5: print("mismatch", pts, ans1, ans2) break

这里比较时用了0.5的容差，因为暴力限制整数中心，而正解允许实数中心，两者最多差0.5左右。实际跑下来，如果公式没写错，10万组随机数据也不会有问题。这个对拍脚本每次写新题我都会复用，能省下大量人工造样例的时间。

4.3 为什么答案和坐标绝对值无关

一个容易忽略的细节是：答案只由u、v的跨度决定，和点的绝对位置无关。把所有点整体平移同样距离，仓库选址问题的答案不会变，因为相对位置完全一样。这在业务上也好理解：整个城市坐标平移，最远配送距离当然不变。

这个性质也能用来做自检。比如把样例每个点都加100，(0,0),(1,1),(2,0)变成(100,100),(101,101),(102,100)，用solve算出来答案仍然是1.0，中心变成(101,100)。如果计算结果出现变化，说明变换公式里混入了不该有的常数项，比如在u或v上多加了偏移量。

另外，u和v的跨度还有一个几何解释：maxU-minU和maxV-minV分别对应点集沿两条45度斜线的投影长度。这两个投影长度中的较大者除以2，恰恰就是曼哈顿距离意义下的最小最大距离。理解这一点之后，很多变体题都能直接套。

4.4 常见错误排查表

我把这个题在调试中容易踩的坑整理成一张表，几乎每一条都有同学在群里问过：

这些坑里，最隐蔽的是“整数中心”那一条。如果业务要求仓库必须落在某个格点上，最优中心附近可能有多个候选点，需要枚举。一般做法是先算出实数中心，再把它上下取整，组合出四个候选点，分别计算最大距离取最小值。它对应的最小最大距离可能比实数解大0.5，所以输出时要用math.ceil。

5. 这个套路还能用到哪些题目上

5.1 最小包围正方形与旋转45度扩展

原题的曼哈顿最大值最小化，本质上是在原坐标系里找一个斜45度的正方形去覆盖所有点，正方形的边和曼哈顿“单位圆”的边缘平行。做完坐标变换之后，正方形边变成轴对齐，于是求最小边长变成算两个方向的跨度。

如果题目本身给的就是切比雪夫距离，要你找一个轴对齐正方形覆盖点集，那甚至不需要换坐标，直接用原坐标的max(maxX-minX, maxY-minY)/2就是答案。如果允许正方形旋转任意角度，问题会变得更难一些，但枚举凸包上的边方向加旋转卡壳也能处理。练题时可以先从0度和45度两个特例入手，感受坐标系移动带来的简化效果。

5.2 反过来用：切比雪夫转曼哈顿的典型场景

有一类题给的是两个点的切比雪夫距离，但要统计“距离小于等于R的点对数量”。如果直接在切比雪夫定义下算，需要二维树状数组或者容斥，比较麻烦。这时候反过来用u=(x+y)/2, v=(x-y)/2变换，切比雪夫距离会变成曼哈顿距离，而曼哈顿距离可以拆成四个方向的偏序关系，再用排序和树状数组解决。

其实很多“旋转坐标系”的经典题都在玩这个互换。比如给定若干点，按曼哈顿距离求最近点对，直接排序x+y、x-y可以降低复杂度；又比如判断“是否存在一个点，使它到所有点的切比雪夫距离都不超过R”，可以转换为检查u、v两个维度的跨度是否都小于等于2R。题目包装千变万化，核心恒等式只有一个。

5.3 两个中心和多目标扩展思路

如果题目变成要选两个仓库，让所有点到最近仓库的最大曼哈顿距离最小，简单公式就不存在了。但解法思路还是顺着坐标变换走：先转成(u,v)切比雪夫距离，然后二分答案R，检查能否用两个轴对齐正方形覆盖所有点。检查函数可以用扫描线按u排序，枚举左侧一个正方形覆盖前缀点，右侧覆盖后缀点。

更高维的情况也有类似技巧，三维切比雪夫距离可以线性时间求最小覆盖立方体半径，公式就是三个维度跨度分别中点。不过高维曼哈顿转切比雪夫就不是每个方向都那么简单，涉及线性代数里的情况。日常刷题先把二维的二维变化玩熟，很多三维题会在二维的基础上套一层前缀和。

我自己每次遇到坐标变换题，都会先在草稿纸上画一个坐标轴，手动把(0,0)、(1,1)、(2,0)这三个点代入公式验证一遍。这个只有三行的手算过程，是防止“公式记反”最有效的方法。另外写代码时也建议用一个断言函数，计算最终中心到每个点的曼哈顿距离并和答案比较，一旦出现偏差立刻暴露问题。这题做完之后最大的收获不是记住这个公式，而是意识到“距离”不是一个固定的东西，换一个坐标系看问题，很多看似复杂的优化目标会自然坍缩成简单的覆盖问题。把L1和L∞之间的这层关系想明白，以后遇到任何带曼哈顿或切比雪夫的题目，都能多一条清晰的解题路径。