35岁大厂程序员上岸武汉体制内，收入从百万年薪锐减到十几万后，妻子嫌弃他没上进心。网友:这种老公，离!

刚看到个贴子，说的是35岁大厂程序员从年薪百万转去武汉体制内，收入直接掉到十几万，结果妻子嫌他没上进心，网友一片“这种老公，离！”的声音。

我觉得这事吧，真没那么简单。贴子里说的是收入落差，但没说清楚的是风险和阶段选择。大厂高薪，本质是拿命换钱，35岁还能不能一直站在牌桌上，谁心里没点数？体制内钱少，但稳定、可预期，这不是摆烂，是换条活法。网友回帖里很多只盯着“钱少了”，却忽略了“风险也小了”，有点站着说话不腰疼。

怎么说呢，婚姻不是KPI，只看当年数值，不看长期曲线。要既要高收入、又要低风险、还要永远年轻，那基本不现实。换个角度想，就像从开快车改成走国道，慢是慢了，但不翻车。

昨天晚上十一点多，我在公司楼下拿奶茶，手机那边我们组小李突然发我一句：哥，平面上最近点对那个算法，你是怎么写的？我当时脑子一抽，想了半天，干脆一边吹风一边跟他语音讲，顺手就把代码敲了一版，你现在看到的就是那个稍微整理了一下的版本。

有一堆点，每个点是 (x, y)，都扔在一个平面上，你要找出两个最近的点之间的距离。就这么简单，不搞花活。

你们肯定第一反应也是这个：既然要找“距离最小”的那一对，那我就把所有两两组合都算一遍，取个 min 就完事了嘛。

伪代码脑补一下就是： “对每个点 i，再对每个点 j>i，算一下距离，更新答案”。

用 Python 写出来大概这样：

import math

defdist(p1, p2):
# p1, p2: (x, y)
    dx = p1[0] - p2[0]
    dy = p1[1] - p2[1]
return math.hypot(dx, dy)  # 等价于 sqrt(dx*dx + dy*dy)

defclosest_pair_bruteforce(points):
    n = len(points)
if n < 2:
return float('inf')  # 没有成对的点

    ans = float('inf')
    pair = None
for i in range(n):
for j in range(i + 1, n):
            d = dist(points[i], points[j])
if d < ans:
                ans = d
                pair = (points[i], points[j])
return ans, pair

这个写起来非常爽，思路也一清二楚，就是时间复杂度是 O(n^2)，点一多的时候会有点顶不住。 你想想，10 万个点，两两组合就是差不多 50 亿次判断，人都麻了。

所以小李问我的时候，我跟他说：这个暴力你写写当然行，但如果是面试或者竞赛题，人家八成是想让你写个 O(n log n) 的版本。

稍微动点脑子：按 x 排序，再“分而治之”

我当时在电梯口等的时候就跟他说，你脑子里先想象一下这样一个场景：

你把所有点按 x 坐标从小到大排好队，竖着砍一刀，一刀把平面分成左右两半。

• 左边那堆点里有一对最近距离 d_left
• 右边那堆点里有一对最近距离 d_right

那整个平面的最近距离，肯定不会比 min(d_left, d_right) 更大，对吧？ 但还有一种情况：最近的那一对点，刚好一个在左边，一个在右边。这就是麻烦的地方。

那问题来了： 既然最小距离不会超过 delta = min(d_left, d_right)，那“跨中线”的最近点对会长啥样？

简单说： 你只需要关心中线附近一条“宽度为 2 * delta 的竖条带子”里的点，离中线太远的点，肯定不可能组成比 delta 更小的距离。这个结论稍微想一下就能接受。

再往下，还有一个非常关键的小结论（这玩意儿是这道题的灵魂）：

在这个竖条带里，如果你把点按 y 坐标排好序，每个点往后最多只需要跟后面有限个点比一下（理论上是 7 个），就能保证不会漏掉最小距离。

这个结论证明过程有点几何味儿，我就不啰嗦了，你先当成“数学家已经帮你证明过”的结论就行，反正我们在代码里只要用就行。

用 Python 写个好理解一点的分治版本

我当时是这么跟他说的：真正的最优解，会在递归里同时维护“按 x 排序”和“按 y 排序”的数组，做到严格的 O(n log n)。但这个实现会稍微绕一点，不太适合在面试现场手写。

所以我先给他写了个好理解一点但稍微慢一点的版本，复杂度大概是 O(n log^2 n)，但是已经比暴力好多了，而且代码也不算丑。

import math

defdist(p1, p2):
    dx = p1[0] - p2[0]
    dy = p1[1] - p2[1]
return math.hypot(dx, dy)

defclosest_pair(points):
# 先按 x 排序一次
    pts = sorted(points, key=lambda p: p[0])

defsolve(l, r):
# 处理区间 [l, r) 的点
        n = r - l
if n <= 3:
# 点很少的时候，直接暴力
            best = float('inf')
            best_pair = None
for i in range(l, r):
for j in range(i + 1, r):
                    d = dist(pts[i], pts[j])
if d < best:
                        best = d
                        best_pair = (pts[i], pts[j])
return best, best_pair

        mid = (l + r) // 2
        mid_x = pts[mid][0]

        d_left, pair_left = solve(l, mid)
        d_right, pair_right = solve(mid, r)

# 先看左右各自内部的最小值
        delta = d_left
        best_pair = pair_left
if d_right < delta:
            delta = d_right
            best_pair = pair_right

# 收集“离中线不超过 delta”的点
        strip = []
for i in range(l, r):
if abs(pts[i][0] - mid_x) <= delta:
                strip.append(pts[i])

# 按 y 排序
        strip.sort(key=lambda p: p[1])

# 在竖条带里检查
        m = len(strip)
for i in range(m):
# 理论上只需要往后看有限几个点
            j = i + 1
while j < m and (strip[j][1] - strip[i][1]) < delta:
                d = dist(strip[i], strip[j])
if d < delta:
                    delta = d
                    best_pair = (strip[i], strip[j])
                j += 1

return delta, best_pair

return solve(0, len(pts))

这个函数 closest_pair(points) 会返回两个东西：

• delta：最近距离
• best_pair：那对最近点

你随便整几个点测一下：

if __name__ == "__main__":
    pts = [(0, 0), (1, 1), (2, 2), (5, 5), (1, 2), (3, 1)]
    d1, pair1 = closest_pair_bruteforce(pts)
    d2, pair2 = closest_pair(pts)
    print("暴力：", d1, pair1)
    print("分治：", d2, pair2)

正常情况下这俩输出的距离是一样的，只是后者在点很多的时候会快非常多。