从激光炮拦截到算法实战二分查找与计算几何的深度碰撞去年国赛那道激光炮的题目不知道有多少同学在考场上卡住了。我当时在监考的时候看到不少选手对着题目发呆明明知道要用二分但就是不知道如何把几何问题转化成可二分的函数。这道题其实是一个绝佳的例子展示了算法竞赛中如何将看似复杂的几何问题通过巧妙的数学建模转化为经典的算法框架。今天我们就来彻底拆解这道题不仅告诉你答案怎么来更重要的是让你掌握这种“转化”的思维。对于参加算法竞赛的选手来说二分查找是基础中的基础但真正能灵活运用的并不多。计算几何更是很多人的软肋一看到坐标系、直线方程就头疼。这道题把两者结合起来考察的恰恰是选手的数学建模能力和算法应用能力。我会用Java和C两种语言来讲解核心思路毕竟在实际比赛中语言选择往往会影响代码实现的细节。1. 问题重述与数学建模从物理场景到数学模型题目描述了一个相当有趣的场景在二维平面上有n门激光炮每门炮都从x-10^5的位置发射目标点是x10^5的位置。我们需要放置一条垂直于x轴的线段来拦截所有激光这条线段的一个端点必须在x轴上我们要找到最短的线段长度。注意这里的关键约束是线段必须垂直于x轴且一端在x轴上。这意味着我们的拦截线段可以沿着x轴上下移动但必须保持竖直方向。1.1 建立坐标系与直线方程首先我们把问题数学化。每门激光炮的发射路径是一条直线连接点(-10^5, a_i)和(10^5, b_i)。由于这两个点的x坐标固定我们可以很容易地求出这条直线的方程。设直线方程为 y kx b其中k是斜率b是截距。根据两点式k_i (b_i - a_i) / (10^5 - (-10^5)) (b_i - a_i) / (2 * 10^5)代入点(-10^5, a_i)a_i k_i * (-10^5) b_i b_i a_i k_i * 10^5实际上我们可以直接计算出截距的简化形式。将k_i的表达式代入b_i a_i [(b_i - a_i)/(2*10^5)] * 10^5 a_i (b_i - a_i)/2 (a_i b_i)/2这个结果很有意思每条激光线的截距恰好是起点纵坐标和终点纵坐标的平均值。这意味着我们不需要存储完整的直线方程只需要记住斜率k和截距b即可。1.2 拦截条件的数学表达现在考虑我们的拦截线段。假设我们在xx0处放置一条竖直线段上端点为(x0, y_top)下端点为(x0, 0)。要拦截第i条激光必须满足在xx0处激光的高度y_i(x0)必须在线段范围内 即0 ≤ y_i(x0) ≤ y_top由于y_top是我们需要最小化的值对于给定的x0最理想的情况是让y_top刚好等于所有激光在x0处的最大高度。这样任何一条激光都不会超过线段的上端点。因此对于固定的x0所需的最小线段长度为f(x0) max_{i1..n} y_i(x0) max_{i1..n} (k_i * x0 b_i)我们的目标就变成了在区间[-10^5, 10^5]上找到一个x0使得f(x0)最小。2. 函数性质分析与二分查找可行性2.1 观察函数f(x)的特性f(x)是n条直线在x处的最大值从几何上看这就是这些直线的上包络线。每条直线y kx b都是一次函数它们的最大值函数f(x)具有什么性质呢让我们把直线按照斜率分类斜率k ≥ 0随着x增大y值单调不减斜率k 0随着x增大y值单调减少设g(x) max_{k≥0} (k_i * x b_i) 所有非负斜率直线的最大值h(x) max_{k0} (k_i * x b_i) 所有负斜率直线的最大值那么 f(x) max(g(x), h(x))关键性质g(x)是单调不减的因为它是单调不减函数的最大值h(x)是单调不增的因为它是单调减少函数的最大值2.2 寻找最小值点由于g(x)递增、h(x)递减它们的最大值函数f(x)的图像大致呈V形或U形。更准确地说f(x)先递减后递增存在一个最小值点。我们可以分几种情况讨论情况条件最小值位置最小值情况1g(-10^5) ≥ h(-10^5)x -10^5f(-10^5)情况2h(10^5) ≥ g(10^5)x 10^5f(10^5)情况3其他中间某点x0f(x0)前两种情况对应最小值在端点处可以直接计算。第三种情况需要找到g(x)和h(x)的交点也就是满足g(x) h(x)的点x0。2.3 二分查找的应用在第三种情况下我们需要找到满足g(x) ≥ h(x)的最小x值。由于g(x)递增、h(x)递减函数d(x) g(x) - h(x)是单调递增的。因此我们可以用二分查找来找到d(x) ≥ 0的最小x。具体来说我们要找的是x0 min{x ∈ [-10^5, 10^5] | g(x) ≥ h(x)}二分查找的判定条件就是检查g(mid) ≥ h(mid)是否成立。如果成立说明答案在左侧或就是mid否则在右侧。3. 算法实现细节与优化3.1 计算g(x)和h(x)的高效方法最直接的方法是遍历所有直线计算最大值但这样每次计算需要O(n)时间。考虑到n最大可达10^5如果二分查找需要几十次迭代总复杂度可能达到O(n log n)在合理范围内。不过我们可以进一步优化。注意到对于固定的x计算g(x)就是求所有非负斜率直线在x处的最大值。由于每条直线都是线性的我们可以预先处理// Java实现预处理斜率分类 ListDouble positiveSlopes new ArrayList(); ListDouble positiveIntercepts new ArrayList(); ListDouble negativeSlopes new ArrayList(); ListDouble negativeIntercepts new ArrayList(); for (int i 0; i n; i) { double k (b[i] - a[i]) / 200000.0; double b_val (a[i] b[i]) / 2.0; if (k 0) { positiveSlopes.add(k); positiveIntercepts.add(b_val); } else { negativeSlopes.add(k); negativeIntercepts.add(b_val); } }3.2 二分查找的精度控制这是一个浮点数二分查找需要特别注意精度问题。题目要求输出保留两位小数这意味着我们的答案误差需要小于0.005。通常的二分查找终止条件是区间长度小于某个阈值。考虑到x的范围是[-10^5, 10^5]区间长度2×10^5要达到0.001的精度大约需要log2(2×10^5/0.001) ≈ 18次迭代。// C实现二分查找框架 double binarySearch(double left, double right) { const double eps 1e-7; // 设置足够小的精度 while (right - left eps) { double mid (left right) / 2; if (check(mid)) { // check函数判断g(mid) h(mid) right mid; } else { left mid; } } return (left right) / 2; }提示在实际竞赛中为了避免浮点数精度问题有时会采用固定次数的迭代比如迭代100次这样通常能保证足够的精度。3.3 边界情况处理需要特别注意两种边界情况所有直线斜率同号如果所有直线斜率都非负那么g(x)就是f(x)最小值在x-10^5处如果所有直线斜率都为负那么h(x)就是f(x)最小值在x10^5处。没有直线虽然题目保证n≥1但在代码中还是应该处理n0的情况返回0。精度误差累积在计算直线值时使用double类型但要注意避免大数相减导致的精度损失。4. 完整代码实现与测试4.1 Java实现import java.util.*; import java.io.*; public class LaserCannon { static class Line { double k, b; Line(double k, double b) { this.k k; this.b b; } double valueAt(double x) { return k * x b; } } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine()); ListLine positive new ArrayList(); ListLine negative new ArrayList(); for (int i 0; i n; i) { String[] parts br.readLine().split( ); int a Integer.parseInt(parts[0]); int b Integer.parseInt(parts[1]); double k (b - a) / 200000.0; double intercept (a b) / 2.0; if (k 0) { positive.add(new Line(k, intercept)); } else { negative.add(new Line(k, intercept)); } } // 计算在x处的最大值 double maxAtX(ListLine lines, double x) { double maxVal -1e18; for (Line line : lines) { maxVal Math.max(maxVal, line.valueAt(x)); } return maxVal; } double g(double x) { return positive.isEmpty() ? -1e18 : maxAtX(positive, x); } double h(double x) { return negative.isEmpty() ? -1e18 : maxAtX(negative, x); } double f(double x) { return Math.max(g(x), h(x)); } // 检查边界情况 double leftX -100000; double rightX 100000; if (g(leftX) h(leftX)) { System.out.printf(%.2f\n, f(leftX)); return; } if (h(rightX) g(rightX)) { System.out.printf(%.2f\n, f(rightX)); return; } // 二分查找 double l leftX, r rightX; for (int iter 0; iter 100; iter) { double mid (l r) / 2; if (g(mid) h(mid)) { r mid; } else { l mid; } } double x0 (l r) / 2; System.out.printf(%.2f\n, f(x0)); } }4.2 C实现竞赛风格#include iostream #include vector #include algorithm #include iomanip #include cmath using namespace std; struct Line { double k, b; double value(double x) const { return k * x b; } }; double maxValueAt(const vectorLine lines, double x) { double res -1e18; for (const auto line : lines) { res max(res, line.value(x)); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorLine pos, neg; for (int i 0; i n; i) { int a, b; cin a b; double k (b - a) / 200000.0; double intercept (a b) / 2.0; if (k 0) { pos.push_back({k, intercept}); } else { neg.push_back({k, intercept}); } } auto g [](double x) - double { return pos.empty() ? -1e18 : maxValueAt(pos, x); }; auto h [](double x) - double { return neg.empty() ? -1e18 : maxValueAt(neg, x); }; auto f [](double x) - double { return max(g(x), h(x)); }; const double LEFT -100000, RIGHT 100000; // 边界情况检查 if (g(LEFT) h(LEFT)) { cout fixed setprecision(2) f(LEFT) endl; return 0; } if (h(RIGHT) g(RIGHT)) { cout fixed setprecision(2) f(RIGHT) endl; return 0; } // 二分查找 double l LEFT, r RIGHT; for (int iter 0; iter 100; iter) { double mid (l r) / 2; if (g(mid) h(mid)) { r mid; } else { l mid; } } double x0 (l r) / 2; cout fixed setprecision(2) f(x0) endl; return 0; }4.3 测试用例验证让我们用题目提供的样例来验证样例输入3 0 100000 100000 200000 200000 0计算过程第一条直线k(100000-0)/2000000.5, b(0100000)/250000第二条直线k(200000-100000)/2000000.5, b(100000200000)/2150000第三条直线k(0-200000)/200000-1.0, b(2000000)/2100000g(x) max(0.5x50000, 0.5x150000) 0.5x150000 (因为15000050000) h(x) -1.0x100000解方程 g(x) h(x) 0.5x150000 -x100000 1.5x -50000 x -100000/3 ≈ -33333.33f(x0) g(-33333.33) 0.5*(-33333.33)150000 ≈ 133333.33与样例输出一致。5. 算法扩展与变式思考5.1 时间复杂度分析让我们分析一下算法的时间复杂度步骤时间复杂度说明数据读取与预处理O(n)读取n条直线按斜率分类边界情况判断O(n)计算g(-10^5)和h(10^5)二分查找迭代O(kn)k次迭代每次计算g(mid)和h(mid)总复杂度O(n log(1/ε))ε为精度要求对于n10^5二分查找100次总操作量约10^7在合理范围内。5.2 优化思路减少每次计算的开销如果n更大比如达到10^6O(n log(1/ε))可能就有些吃力了。我们可以考虑以下优化预处理极值直线对于g(x)我们实际上只需要考虑那些在某个区间上可能成为最大值的直线。这可以通过计算直线的交点来筛选。使用凸包技巧对于斜率同号的直线集合最大值函数实际上是一个凸包上凸壳。我们可以先求出凸包然后在凸包上二分查找。// 优化思路构建凸包 ListLine buildUpperHull(ListLine lines) { // 按斜率排序斜率相同的保留截距最大的 lines.sort((l1, l2) - { if (Math.abs(l1.k - l2.k) 1e-9) { return Double.compare(l2.b, l1.b); // 截距大的优先 } return Double.compare(l1.k, l2.k); }); ListLine hull new ArrayList(); for (Line line : lines) { // 移除不会成为最大值的直线 while (hull.size() 2) { Line last hull.get(hull.size() - 1); Line secondLast hull.get(hull.size() - 2); // 检查交点 double xIntersect (last.b - secondLast.b) / (secondLast.k - last.k); double newIntersect (line.b - last.b) / (last.k - line.k); if (newIntersect xIntersect) { hull.remove(hull.size() - 1); } else { break; } } hull.add(line); } return hull; }5.3 相关题目与变式掌握了这道题的核心思想后可以尝试解决一些变式问题拦截线段方向可变如果拦截线段可以不垂直于x轴而是可以旋转问题就变成了求最小覆盖线段难度会大大增加。三维空间中的拦截将问题扩展到三维空间激光从平面发射拦截物是一个平面或球体。动态添加激光炮支持在线添加新的激光炮需要动态维护答案。拦截线段有长度限制线段长度不能超过L求是否能拦截所有激光。5.4 实际应用场景这种类型的问题不仅在竞赛中出现在实际工程中也有应用雷达干扰屏蔽计算最小屏蔽区域来阻挡所有干扰信号网络安全在流量监控中识别异常连接模式机器人路径规划避免与多条动态障碍物轨迹相交无线网络优化放置中继器以覆盖所有通信链路6. 竞赛实战技巧与常见陷阱6.1 浮点数处理要点在算法竞赛中浮点数计算是常见的坑点。以下是一些实用技巧避免直接比较相等使用eps比较const double eps 1e-9; bool equal(double a, double b) { return fabs(a - b) eps; }二分查找的迭代次数固定迭代次数比判断区间长度更稳定for (int i 0; i 100; i) { double mid (left right) / 2; // ... }输出精度控制题目要求保留2位小数要使用正确的格式化System.out.printf(%.2f\n, result); // 注意这会自动四舍五入6.2 边界条件测试在编写完代码后一定要测试以下边界情况n1只有一条激光所有a_ib_i激光水平发射a_i和b_i很大接近10^6的情况斜率非常接近测试浮点数精度对称情况a_i和b_i对称分布这里提供一个简单的测试框架void test() { // 测试1: 样例 testCase(new int[][]{{0, 100000}, {100000, 200000}, {200000, 0}}, 133333.33); // 测试2: 所有激光平行 testCase(new int[][]{{0, 0}, {1000, 1000}, {2000, 2000}}, 100000.00); // 测试3: 单条激光 testCase(new int[][]{{500000, 500000}}, 500000.00); // 测试4: 对称情况 testCase(new int[][]{{0, 100000}, {100000, 0}}, 50000.00); } void testCase(int[][] data, double expected) { // 实现测试逻辑 double result solve(data); if (Math.abs(result - expected) 0.01) { System.out.println(PASS); } else { System.out.printf(FAIL: expected %.2f, got %.2f\n, expected, result); } }6.3 性能优化建议对于大数据量n10^5还需要注意使用快速IO在Java中使用BufferedReader在C中使用scanf/printf或关闭同步避免不必要的对象创建在循环中重用对象使用原生数组代替集合如果性能关键使用double[]代替ArrayList减少函数调用开销将小函数内联// 优化后的计算函数 double computeMax(double x, double[] slopes, double[] intercepts) { double max -Double.MAX_VALUE; for (int i 0; i slopes.length; i) { double val slopes[i] * x intercepts[i]; if (val max) max val; } return max; }6.4 调试技巧当代码出现问题时可以输出中间结果打印g(x)和h(x)的值观察单调性可视化对于小数据可以画图观察函数形状对拍写一个暴力解法O(n^2)对小数据进行测试边界测试特别测试x-10^5和x10^5的情况我在实际比赛中就遇到过类似的问题当时因为没有正确处理所有斜率同号的情况导致了一个测试点没过。后来发现当所有直线斜率都为正时最小值确实在左端点但我的代码却进入了二分查找分支。这个教训让我意识到边界情况的处理往往比核心算法更重要。7. 从这道题看算法竞赛的解题思维这道激光炮题目很好地体现了算法竞赛的解题流程问题理解与抽象将物理场景转化为数学模型性质分析发现函数单调性确定可二分性算法设计设计二分查找框架实现与优化编写高效代码处理边界情况测试验证确保正确性和性能这种思维模式不仅适用于这道题对于大多数竞赛题目都适用。我经常告诉学生看到题目不要急着写代码先花5-10分钟分析问题性质往往能事半功倍。对于计算几何类题目有几个通用技巧坐标变换简化问题凸包思想处理最大值/最小值函数扫描线算法处理区间覆盖二分答案当答案具有单调性时这道题还有一个值得注意的地方它没有用到复杂的几何计算如向量叉积、点积等而是通过代数方法简化了问题。这提醒我们有时候避开几何计算用代数视角看问题会更简单。在实际编码时我建议先写一个暴力版本验证思路再逐步优化。比如可以先写一个O(n^2)的解法枚举所有可能的x值离散化验证二分查找的正确性。这样虽然效率低但能确保思路正确避免在复杂优化中迷失方向。最后关于这道题的难度我认为它属于中等偏上。它考察的不是某个特定的高级算法而是综合运用基础算法二分查找解决实际问题的能力。这种能力正是算法竞赛要培养的核心能力之一。在平时的训练中应该多做一些这种需要建模和转化的题目而不是只刷模板题。