城市信号塔最小距离：最近点对分治算法与O(N log N)优化实战-北京尧图网络

秋招的笔试题目刷多了你会发现很多200分题看着吓人实际考的却是一些非常基础的算法底子。今天要拆解的这道“城市信号塔的最小距离”表面是算一堆坐标点里最近的两个点距离本质上就是把“最近点对”这个经典模型换了一层通信行业的皮。2025年秋招非AI方向的同学无论是通软、嵌入式、测试还是数据科学岗位都可能在笔试卷上遇到类似题因为它在考察排序、分治、边界处理和复杂度优化几乎个个都是基本功。本文会把题目还原、思路推导、三种语言实现、在线测试和避坑经验一次讲透。1. 题目到底在考什么1.1 原题描述与数据范围我按实际考试场景尽量还原题目一座城市里部署了 N 座信号塔每座塔的坐标是 (x_i, y_i)。为了避免信号互相干扰需要评估当前所有信号塔之间的最小距离。请计算所有信号塔两两之间欧几里得距离的平方的最小值。如果两座塔部署在同一位置最小距离视为 0。输入格式第一行一个整数 N表示信号塔数量。接下来 N 行每行两个整数 x_i 和 y_i表示第 i 座塔的坐标。坐标范围-10^9 ≤ x_i, y_i ≤ 10^9N 最大 10^5。输出一个整数即最小的距离平方。注意这里为什么要输出平方而不是距离本身。因为坐标全是整数距离平方一定是整数判题机不需要处理浮点误差选手也不需要去背“保留两位小数”这种输出格式。很多最近点对的题目都采用“输出距离平方”的设计这也是一个很有效的防误差手段后面写代码时我们会一直使用整数运算。一个简单示例输入 4 0 0 1 1 2 2 3 3 输出 2四个点连成一条斜率 1 的直线相邻点之间的距离平方是 (1-0)^2 (1-0)^2 2所以答案是 2。1.2 它对应的经典模型最近点对这道题剥掉“信号塔”外衣之后就是平面点集上的最近点对问题给一堆二维平面上的整数点求所有点对中欧几里得距离平方的最小值。这个模型在很多领域都有影子比如雷达目标聚类、基站选址、碰撞检测、地图点位聚合等。很多同学第一反应是两重循环暴力枚举所有点对确实简单但在 N10^5 时完全不可行。两两组合总数约为 N(N-1)/2 5×10^9即使每次比较只是几次乘法和加法现代 CPU 也扛不住判题机更不可能给你这么长的运行时间。所以题目真正的考察点不是“你会不会算距离”而是“你能不能把一个 O(N^2) 问题优化到 O(N log N)”。这里也是秋招笔试常见的小陷阱200分题不一定难但它一定需要你做复杂度分析。如果一上来就写暴力小数据样例能过大数据直接超时这种“样例全过但提交超时”的情况是最可惜的。1.3 数据范围决定了必须用分治或扫描线当 N 到 10^5 这个量级能接受的复杂度通常是 O(N log N) 或者更优。平面最近点对这个模型里最经典的解法就是分治法另外也能用扫描线法做前者在笔试中更常被考察。顺手算一下复杂度暴力是 O(N^2)排序后分治是 O(N log N)两者在 N10^5 时相差大约 10^5 倍这完全决定了你能不能拿到这 200 分。理解这个数量级差异是解这道题的第一步。2. 从暴力的 O(N^2) 到分治的 O(N log N)2.1 暴力解法与复杂度估算我们先写一个最朴素的想法两层 for 循环枚举 i j不断更新最小距离平方。伪代码大概是ans INF for i in range(N): for j in range(i 1, N): ans min(ans, dist2(p[i], p[j]))这段代码绝对正确任何一本算法书都不会说它错但它只适合 N 很小的情况。当 N10^5内层循环总执行次数是 5×10^9假设每秒能跑 10^9 次简单操作也要好几秒甚至更久并且每次操作还不止一条机器指令。笔试环境通常会限制 1 到 2 秒暴力基本必挂。但这不意味着暴力没用。实际调试时暴力代码是验证高效算法正确性的对拍基准。先写一个暴力版再去写分治版然后随机生成小规模数据对比结果这是我在笔试和平时练习中一直推荐的做法。2.2 分治核心思想按 x 坐标切一半分治法的思想和“归并排序”很像先把所有点按照 x 坐标排序然后从中间切一刀把点集分成左右两个规模大致相等的子集。假设我们递归求出了左半部分内部的最近距离 d1右半部分内部的最近距离 d2那么当前区间内可能的最近点对只有三种来源两个点都在左半部分两个点都在右半部分一个点在左半部分一个点在右半部分。前两种情况已经由递归返回的 d1 和 d2 覆盖我们只需要重点处理第三种情况。设当前最优值 d min(d1, d2)。要跨越中线产生比 d 更小的距离两个点的 x 坐标离中线的距离都必须小于 sqrt(d)也就是 x 方向的差绝对值必须小于 sqrt(d)。在代码里我们直接比较平方即 (x - mid_x)^2 d这样就可以避免开根号全程整数运算。这一步就是分治法的核心把跨中线点对的数量从 O(N^2) 压缩到 O(N)因为真正需要检查的点只会落在一个很窄的条带里。2.3 为什么条带内只需要检查常数个点很多人卡在“条带内点还是很多啊会不会退化”这个问题上。关键结论是条带内每个点最多只需要和按 y 排序后紧随其后的少数几个点比较。给一个直观解释。假设当前最优距离是 d跨中线点对如果要优于 d那么这两个点的 y 坐标差的平方也必须小于 d。也就是说对于条带内某一个点 P我们只需要检查那些在 y 方向上离 P 不超过 sqrt(d) 的点。因为我们把条带里的点按 y 坐标排序后一旦发现某个点与 P 的 y 差平方已经大于等于 d再往后的点更不可能比 d 优直接退出内层循环。更严格地说在高度为 sqrt(d)、宽度为 2*sqrt(d) 的条带区域内能够放置的、任意两点距离不小于 sqrt(d) 的点数存在一个常数上界通常证明可以把这个矩形划分成若干小格子每个小格子内至多一个点总数不超过 7 个或者 8 个。所以每个点最多和后面 7 个左右点比较内层循环是常数次。正是因为有了这个几何性质分治才能做到 O(N log N)。这个证明我在面试时被追问过建议你也准备一下数学上计算的是 dd_d 的常数实际代码里我们直接用dy * dy d来做 break效果一样而且不会出错。2.4 时间复杂度推导与实现策略按上面方案递归公式是 T(N) 2*T(N/2) O(N)。左边一半右边一半合并时要把左右两边已经在子递归里按 y 排好序的点归并一次这个过程是 O(N)。所以最终复杂度是 T(N) O(N log N)空间复杂度是 O(N)。这里要特别说一个实现细节。如果我们在每一层递归中都单独把条带内的点再重新按 y 排一次序那么合并阶段的复杂度会变成 O(N log N)总复杂度就会到 O(N log^2 N)。虽然 N10^5 时 C 和 Java 通常也能跑过但严格来说不够优雅Python 则可能比较勉强。更好的写法是采用类似归并排序的策略递归返回时让当前区间内的点已经按 y 坐标有序这样上层归并时直接线性合并即可不需要再排序。三种语言的代码都会用这个更优的写法因为这才是真正的 O(N log N)。3. 三种语言的代码实现与关键细节3.1 Java 实现注意用 long 防溢出Java 代码里最大的坑是类型。两点坐标差值最大可能是 2×10^9平方之后是 4×10^18两个方向相加是 8×10^18已经接近 long 的最大值 9.22×10^18但不会超所以必须用 long不能用 int。import java.io.*; import java.util.*; public class Main { static long best; static Point[] p; static Point[] aux; static Point[] strip; static class Point { long x, y; Point(long x, long y) { this.x x; this.y y; } } static long dist2(Point a, Point b) { long dx a.x - b.x; long dy a.y - b.y; return dx * dx dy * dy; } static void insertionSortByY(int l, int r) { for (int i l 1; i r; i) { Point key p[i]; int j i - 1; while (j l p[j].y key.y) { p[j 1] p[j]; j--; } p[j 1] key; } } static void solve(int l, int r) { if (l r) return; if (r - l 3) { for (int i l; i r; i) { for (int j i 1; j r; j) { best Math.min(best, dist2(p[i], p[j])); } } insertionSortByY(l, r); return; } int mid (l r) 1; long midX p[mid].x; solve(l, mid); solve(mid 1, r); int i l, j mid 1, k l; while (i mid j r) { if (p[i].y p[j].y) aux[k] p[i]; else aux[k] p[j]; } while (i mid) aux[k] p[i]; while (j r) aux[k] p[j]; int cnt 0; for (int t l; t r; t) { long dx aux[t].x - midX; if (dx * dx best) { strip[cnt] aux[t]; } } for (int a 0; a cnt; a) { Point pa strip[a]; for (int b a 1; b cnt; b) { long dy strip[b].y - pa.y; if (dy * dy best) break; best Math.min(best, dist2(pa, strip[b])); } } for (int t l; t r; t) { p[t] aux[t]; } } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine().trim()); if (n 2) { System.out.println(0); return; } p new Point[n]; aux new Point[n]; strip new Point[n]; for (int i 0; i n; i) { StringTokenizer st new StringTokenizer(br.readLine()); long x Long.parseLong(st.nextToken()); long y Long.parseLong(st.nextToken()); p[i] new Point(x, y); } Arrays.sort(p, new ComparatorPoint() { public int compare(Point a, Point b) { if (a.x ! b.x) return Long.compare(a.x, b.x); return Long.compare(a.y, b.y); } }); best Long.MAX_VALUE; solve(0, n - 1); System.out.println(best); } }说几个 Java 特有的注意点用BufferedReader代替Scanner我在笔试中实测差距非常大数据量大时 Scanner 可能直接拖慢到超时。mid用(l r) 1而不是(l r) / 2能够避免大数组下索引溢出虽然这里 N 才 10^5 不会溢出但这是好习惯。aux和strip都直接用成员数组复用不要在递归里频繁new否则堆分配会成为性能瓶颈。3.2 C 实现最接近标准模板的版本C 写这个题会比较顺手vector 和 sort 都比 Java 简洁但还是有几处值得注意坐标和中间变量全部用long long比较距离时用LLONG_MAX初始化 best。#include bits/stdc.h using namespace std; struct Point { long long x, y; }; long long best; vectorPoint p, aux, strip; long long dist2(const Point a, const Point b) { long long dx a.x - b.x; long long dy a.y - b.y; return dx * dx dy * dy; } void insertionSortByY(int l, int r) { for (int i l 1; i r; i) { Point key p[i]; int j i - 1; while (j l p[j].y key.y) { p[j 1] p[j]; --j; } p[j 1] key; } } void solve(int l, int r) { if (l r) return; if (r - l 3) { for (int i l; i r; i) { for (int j i 1; j r; j) { best min(best, dist2(p[i], p[j])); } } insertionSortByY(l, r); return; } int mid (l r) 1; long long midX p[mid].x; solve(l, mid); solve(mid 1, r); int i l, j mid 1, k l; while (i mid j r) { if (p[i].y p[j].y) aux[k] p[i]; else aux[k] p[j]; } while (i mid) aux[k] p[i]; while (j r) aux[k] p[j]; int cnt 0; for (int t l; t r; t) { long long dx aux[t].x - midX; if (dx * dx best) strip[cnt] aux[t]; } for (int a 0; a cnt; a) { for (int b a 1; b cnt; b) { long long dy strip[b].y - strip[a].y; if (dy * dy best) break; best min(best, dist2(strip[a], strip[b])); } } for (int t l; t r; t) p[t] aux[t]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; if (n 2) { cout 0 \n; return 0; } p.resize(n); for (int i 0; i n; i) { cin p[i].x p[i].y; } sort(p.begin(), p.end(), [](const Point a, const Point b) { if (a.x ! b.x) return a.x b.x; return a.y b.y; }); aux.resize(n); strip.resize(n); best LLONG_MAX; solve(0, n - 1); cout best \n; return 0; }C 里最容易翻车的地方是int和long long混用。坐标差值计算时如果中间变量是 int乘出来的结果会先溢出再被赋值给 long long那就全乱了。建议所有坐标、距离、midX、best 全部一条道走到底统一long long不要混用。3.3 Python 实现递归深度与性能优化Python 版本最需要注意递归深度。N10^5 时分治递归深度是 O(log N)大约 17 层左右默认 1000 深度完全够但我习惯一开始就sys.setrecursionlimit(1_000_000)保险因为别的题目可能也需要。import sys sys.setrecursionlimit(1_000_000) def main(): data sys.stdin.buffer.read().split() if not data: return it iter(data) n int(next(it)) if n 2: print(0) return points [(int(next(it)), int(next(it))) for _ in range(n)] points.sort(keylambda p: (p[0], p[1])) best 10 ** 30 aux [None] * n strip [None] * n def dist2(a, b): dx a[0] - b[0] dy a[1] - b[1] return dx * dx dy * dy def insertion_sort_y(l, r): for i in range(l 1, r 1): key points[i] j i - 1 while j l and points[j][1] key[1]: points[j 1] points[j] j - 1 points[j 1] key def solve(l, r): nonlocal best if l r: return if r - l 3: for i in range(l, r 1): for j in range(i 1, r 1): d dist2(points[i], points[j]) if d best: best d insertion_sort_y(l, r) return mid (l r) // 2 mid_x points[mid][0] solve(l, mid) solve(mid 1, r) i, j, k l, mid 1, l while i mid and j r: if points[i][1] points[j][1]: aux[k] points[i] i 1 else: aux[k] points[j] j 1 k 1 while i mid: aux[k] points[i] i 1 k 1 while j r: aux[k] points[j] j 1 k 1 cnt 0 for t in range(l, r 1): dx aux[t][0] - mid_x if dx * dx best: strip[cnt] aux[t] cnt 1 for a in range(cnt): pa strip[a] for b in range(a 1, cnt): dy strip[b][1] - pa[1] if dy * dy best: break d dist2(pa, strip[b]) if d best: best d points[l:r 1] aux[l:r 1] solve(0, n - 1) print(best) if __name__ __main__: main()Python 的切片赋值points[l:r1] aux[l:r1]会把这一段改成 aux 对应位置的引用后面递归不会再访问旧对象所以没有隐患。性能方面因为内层每个点平均只比常数个点主体循环量不大1e5 数据在 OJ 上通常是能过的。如果你遇到特别严苛的时限可以考虑把insertion_sort_y合并进普通排序逻辑或者在主循环里用局部变量缓存aux和strip的引用尽量减少属性查找。3.4 三个版本共用的边界处理和坑点三个语言版本都保留了同一个关键逻辑当n 2时直接输出 0。这一点看着不起眼但如果不处理best会保持初始值Long.MAX_VALUE或LLONG_MAX输出一个巨大的数字直接判错。N1 的测试点在笔试里经常出现专门用来抓这种边界疏忽。另一个共用坑点是在条带扫描里break 条件必须是dy * dy best。如果你写成 best当 dy 的平方恰好等于当前最优值时你还继续往下比虽然不会算错但会多比较很多点极端情况下可能退化。这个细节也体现对分治原理的理解。还要注意排序的比较器。主排序必须按 x 为第一关键字y 为第二关键字。分治划分时用mid (l r) / 2如果 x 相同但 y 乱序中点选择依然稳定不会影响正确性但统一排序会让代码行为更可预期。4. 在线测试与对拍验证4.1 手工构造必测样例代码写完之后不要急着直接交先用手工样例把逻辑走一遍。我整理了几组必测数据N2 的简单情况比如 (0,0) 和 (3,4)正确答案是 25。所有点共线比如 x 全部相同只有 y 变化这时最近点对一定在相邻点之间。所有点重合比如五个点都是 (1,1)正确答案是 0。坐标接近 1e9 的极端值比如 (-1e9, -1e9) 和 (1e9, 1e9)距离平方是 8e18仍然在 long 范围内但漏用 long 会立刻溢出。N1 的边界情况按我们设定输出 0。这些样例看着简单却能精准打击实现中的类型溢出和边界遗漏。4.2 随机数据对拍模板更可靠的验证方式是随机对拍。先写一个暴力函数def brute(points): ans 10 ** 30 n len(points) for i in range(n): for j in range(i 1, n): dx points[i][0] - points[j][0] dy points[i][1] - points[j][1] ans min(ans, dx * dx dy * dy) return ans再用随机数生成小规模点集把暴力结果和分治结果对比import random for n in range(2, 30): for _ in range(300): pts [(random.randint(-10, 10), random.randint(-10, 10)) for _ in range(n)] b brute(pts) f fast_closest_pair(pts) # 这里调用你写成独立函数的分治版本 if b ! f: print(error:, pts, b, f) break对拍范围选择坐标 -10 到 10规模 n 到 30 就足够因为分治逻辑与坐标范围无关小范围更容易出现重合点、等距点等临界情况。多跑几百组比只看几个样例放心得多。4.3 性能实测与优化建议如果手边有在线评测环境可以直接生成 N10^5 的随机点来测耗时。我在自己电脑上测过上面这套代码C 版本一般在 0.1 秒以内。Java 版本大概 0.2 到 0.3 秒主要开销在对象数组访问。Python 版本稍慢但也能在 2 秒内完成。如果 Python 版本超时优先检查是不是在递归里写成了“每层都对条带重新排序”那个版本复杂度是 O(N log^2 N)随机数据下容易被卡。改用归并维护 y 序之后性能基本就稳了。还有一个很容易被忽视的优化输入读取。Python 里用sys.stdin.buffer.read()一次性读取全部数据再 split比逐行input()快非常多。Java 里尽量用BufferedReaderC 里加上ios::sync_with_stdio(false)。这些IO优化在 1e5 量级可能感觉不明显但到了更大数据量差距会非常直观。5. 从这道题延伸出去5.1 最近点对的几个常见变体这道题掌握了可以顺手扩展几个变体一维最近点对把所有点按坐标排序后答案一定出现在相邻点之间这是最简单的情况。判断是否存在距离不超过 K 的点对可以直接在分治过程中剪枝一旦发现距离小于等于 K 就提前返回。输出最近点对的坐标而不只是距离更新 best 的同时记录对应的两个点即可代码改动很小。求所有点对中的最大距离那是凸包问题和最近点对思路完全不同别混淆。面试时如果时间充裕还可以提一下扫描线解法按 x 排序后用平衡树维护当前窗口内点的 y 坐标每个点只和窗口内几个点比较。这个思路在动态增量场景下更有用但在笔试里分治已经足够没必须给自己增加实现难度。5.2 秋招笔试现场的做题策略200分题在整套试卷里通常属于“中等偏上”的位置我的建议是不要先埋头写代码先花两分钟判断题目类型。看到“坐标”“最小距离”“N 很大”这些关键词就应该迅速联想到最近点对、凸包、最小生成树这几个几何模型。这道题最大的陷阱不是难度而是很多人第一眼觉得“这不就是暴力吗”结果浪费大把时间写完一提交就超时。合理策略是先想清楚算法复杂度再用最小实现成本写一个暴力版验证小样例最后实现高效版本。笔试环境时间紧张但“先暴力再优化”往往比“一上来就憋最优解”更稳因为暴力版本至少能保证你在小数据上拿分也能成为对拍基准。5.3 个人复盘与一个小技巧我在实际练习这道题时最深刻的体会是分治法的代码不难抄真正难的是理解“为什么条带内最多查常数个点”。建议你亲手画一下那个 2d × sqrt(d) 的矩形区域先画出左右区域内部任意两点距离都 ≥ sqrt(d) 的条件再去数矩形内最多能放几个点。画过一遍之后这个题就不再是背诵代码而是真正内化了。最后再分享一个排查技巧如果分治结果和暴力结果不一致优先怀疑边界索引。比如递归区间是[l, mid]还是[l, mid]加[mid1, r]归并时循环条件有没有漏掉i mid条带筛选用的是aux还是已经变动的p。这些地方随便错一处结果就会非常难调。把递归入口和边界条件打印出来配合小数据集很快就能定位问题。

城市信号塔最小距离：最近点对分治算法与O(N log N)优化实战

相关推荐

混合量子-经典模型破解网络攻击路径分析难题

千笔与WPS AI：专科生开题报告卡壳的破解之道

artcraft工作流：从概念到实物的数字手工融合实践

更多资讯

国内大模型长期使用选型指南：稳定、嵌入、安全、可维的四维评估法

五大主流AI图像生成模型实测与选型指南

MIMO波束成形MATLAB仿真：从信道建模到ZF/MMSE检测完整指南

模型预测控制与扰动观测器：提升PMSM鲁棒性的工程实践

Artcraft：人机协作的决策分层与触觉断点设计

Python Django构建图书管理系统：从模型设计到部署实战

今日更新

智能硬件视频会议集成：从芯片选型到场景落地的全栈实践

FFmpeg音视频处理与5路RTMP推流实战：从原理到118克盒子部署

RK3528+1GB内存如何变身直播节点？硬编解码与六协议实战复盘

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？