最小覆盖圆问题：华为机试中的信号塔最优选址算法

最小覆盖圆问题：华为机试中的信号塔最优选址算法

发布时间：2026/8/22 8:27:09
最小覆盖圆问题：华为机试中的信号塔最优选址算法 1. 题目解析与需求拆解这道华为秋招机试题的核心是在二维平面上给定N个信号塔的坐标要求找到一个点使得该点到所有信号塔的最大距离最小化。这个问题在数学上被称为最小覆盖圆问题或最小最大距离问题在通信基站选址、物流中心规划等领域有广泛应用。1.1 问题形式化描述给定N个信号塔的坐标 (x₁,y₁), (x₂,y₂), ..., (xₙ,yₙ)要求找到一个点 (a,b)使得 max(√[(a-x₁)²(b-y₁)²], ..., √[(a-xₙ)²(b-yₙ)²]) 最小1.2 实际应用场景这个问题在通信网络规划中非常常见。比如5G基站选址时需要确保覆盖区域内所有用户设备的最大信号延迟最小无人机充电站布置需要让任意位置的无人机都能在最短距离内找到充电站应急广播系统需要确保任何位置都能接收到至少一个信号塔的广播2. 算法思路分析2.1 暴力解法及其局限性最直观的想法是枚举平面上所有可能的点计算每个点到所有信号塔的最大距离然后取最小值。但这种方法时间复杂度极高无限多个点无法在有限时间内得到精确解2.2 几何解法最小覆盖圆这个问题在计算几何中有标准解法——Welzl算法可以在O(n)时间复杂度内找到最小覆盖圆。其核心思想是随机排列所有点初始时圆为空对于每个点如果不在当前圆内则将该点作为新圆上的点递归处理前面的点2.3 数值解法三分搜索对于编程竞赛更实用的方法是三分搜索先固定x坐标对y坐标进行三分搜索找到当前x下的最优y再对x坐标进行三分搜索通过双重三分逼近最优解这种方法时间复杂度约为O(log²(1/ε))其中ε是精度要求。3. Java实现与解析import java.util.*; public class Main { static class Point { double x, y; Point(double x, double y) { this.x x; this.y y; } } static Point[] points; static final double EPS 1e-8; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); points new Point[n]; for(int i0; in; i) { double x sc.nextDouble(); double y sc.nextDouble(); points[i] new Point(x, y); } // 三分搜索x坐标 double left -1e4, right 1e4; while(right - left EPS) { double mid1 left (right - left)/3; double mid2 right - (right - left)/3; if(calc(mid1) calc(mid2)) { left mid1; } else { right mid2; } } double bestX (left right)/2; double bestY findY(bestX); double minDist maxDistance(bestX, bestY); System.out.printf(%.2f, minDist); } // 给定x找到最优y static double findY(double x) { double left -1e4, right 1e4; while(right - left EPS) { double mid1 left (right - left)/3; double mid2 right - (right - left)/3; if(maxDistance(x, mid1) maxDistance(x, mid2)) { left mid1; } else { right mid2; } } return (left right)/2; } // 计算给定x时的最小最大距离 static double calc(double x) { double y findY(x); return maxDistance(x, y); } // 计算点(x,y)到所有信号塔的最大距离 static double maxDistance(double x, double y) { double max 0; for(Point p : points) { double dx x - p.x; double dy y - p.y; max Math.max(max, Math.sqrt(dx*dx dy*dy)); } return max; } }3.1 关键点解析三分搜索实现对x和y坐标分别进行三分搜索逐步缩小最优解范围精度控制使用EPS1e-8作为终止条件确保结果精确到小数点后两位函数分解maxDistance()计算给定点到所有信号塔的最大距离findY()对给定x坐标找到最优y坐标calc()封装双重三分搜索过程3.2 复杂度分析时间复杂度O(n log²(1/ε))其中n是信号塔数量ε是精度要求空间复杂度O(n)用于存储信号塔坐标4. C实现与解析#include iostream #include vector #include cmath #include iomanip using namespace std; const double EPS 1e-8; struct Point { double x, y; Point(double x0, double y0):x(x),y(y){} }; vectorPoint points; double max_distance(double x, double y) { double max_dist 0; for(auto p : points) { double dx x - p.x; double dy y - p.y; max_dist max(max_dist, sqrt(dx*dx dy*dy)); } return max_dist; } double find_y(double x) { double left -1e4, right 1e4; while(right - left EPS) { double mid1 left (right - left)/3; double mid2 right - (right - left)/3; if(max_distance(x, mid1) max_distance(x, mid2)) { left mid1; } else { right mid2; } } return (left right)/2; } double calc(double x) { double y find_y(x); return max_distance(x, y); } int main() { int n; cin n; points.resize(n); for(int i0; in; i) { cin points[i].x points[i].y; } // 三分搜索x坐标 double left -1e4, right 1e4; while(right - left EPS) { double mid1 left (right - left)/3; double mid2 right - (right - left)/3; if(calc(mid1) calc(mid2)) { left mid1; } else { right mid2; } } double best_x (left right)/2; double best_y find_y(best_x); double min_dist max_distance(best_x, best_y); cout fixed setprecision(2) min_dist endl; return 0; }4.1 C特性利用结构体构造使用构造函数简化Point对象的创建IO优化fixed和setprecision控制输出格式STL容器使用vector存储点集方便动态调整大小4.2 性能考虑C实现通常比Java更快特别是避免Java的自动装箱/拆箱更直接的内存访问更高效的数学函数实现5. Python实现与解析import math def main(): import sys input sys.stdin.read data input().split() n int(data[0]) points [] index 1 for _ in range(n): x float(data[index]) y float(data[index1]) points.append((x, y)) index 2 EPS 1e-8 def max_distance(x, y): max_dist 0 for (px, py) in points: dx x - px dy y - py dist math.sqrt(dx*dx dy*dy) if dist max_dist: max_dist dist return max_dist def find_y(x): left, right -1e4, 1e4 while right - left EPS: mid1 left (right - left)/3 mid2 right - (right - left)/3 if max_distance(x, mid1) max_distance(x, mid2): left mid1 else: right mid2 return (left right)/2 def calc(x): y find_y(x) return max_distance(x, y) # 三分搜索x坐标 left, right -1e4, 1e4 while right - left EPS: mid1 left (right - left)/3 mid2 right - (right - left)/3 if calc(mid1) calc(mid2): left mid1 else: right mid2 best_x (left right)/2 best_y find_y(best_x) min_dist max_distance(best_x, best_y) print({0:.2f}.format(min_dist)) if __name__ __main__: main()5.1 Python实现特点输入处理使用sys.stdin.read快速读取所有输入适用于编程竞赛环境嵌套函数利用Python的嵌套函数特性使代码结构更清晰精度控制虽然Python浮点数精度足够但仍需注意EPS的合理设置5.2 性能优化建议对于大规模数据可以考虑使用NumPy数组存储点集使用向量化运算替代循环对于特别大的n可能需要更高效的算法6. 测试用例设计6.1 基础测试用例3 0 0 3 0 0 4预期输出2.50 解释最优点在(1.5,2)最大距离为2.56.2 边界情况1 5 5预期输出0.00 解释只有一个信号塔最优位置就是信号塔本身6.3 大规模测试10 1.2 3.4 5.6 7.8 9.0 1.2 3.4 5.6 7.8 9.0 2.3 4.5 6.7 8.9 0.1 2.3 4.5 6.7 8.9 0.1预期输出5.00近似值实际需要计算7. 算法优化与变种7.1 迭代优化法除了三分搜索还可以使用梯度下降等迭代方法随机初始化一个点计算当前点到各信号塔的距离梯度沿着梯度方向更新点位置重复直到收敛7.2 加权最小最大距离实际问题中不同信号塔可能有不同权重目标变为最小化 max(wᵢ·distance(p,pᵢ))算法需要相应调整但基本思路类似7.3 高维扩展在三维空间中如无人机基站布置需要增加对z坐标的搜索基本算法框架不变但计算量会增加8. 华为OD机考注意事项输入输出格式严格按照题目要求包括小数点位数时间限制Python实现可能需要注意优化避免超时边界检查考虑n1等特殊情况代码风格保持整洁适当注释方便阅卷提示在实际机考中建议先写暴力解法确保正确性再优化为高效算法。三分搜索的实现需要特别注意终止条件和更新规则避免无限循环。