贝壳找房 · 计算几何 · 算法编程题
贝壳找房 计算几何 n ≤ 200000 时限 1 秒 / 256 MB

题目描述

在工厂中，有 N 个牛牛工作在一个流水线上，流水线可以看作一个坐标轴，第 i 个牛牛的位置是 X_i ，延长其手臂的长度为 L_i ，手臂可以朝向正向和反向，即第 i 个牛牛在流水线的工作范围为 [X_i - L_i,X_i + L_i] ，你需要计算最多可以让多少个牛牛同时在流水线上工作且工作范围互不相交（只交在一个点也算相交）。

输入输出

输入描述
第一行一个整数 n ， 1 ≤ n ≤ 2 × 10^5
接下来 n 行，每行 2 个整数 X_i , L_i (0 ≤ X_i ≤ 10^9,1 ≤ L_i ≤ 10^9)
所有的输入为整数，且 i ≠ j 时， X_i ≠ X_j .
输出描述
一行一个整数代表答案

样例共 3 组

样例 1
输入
5
2 3
7 1
5 1
8 3
0 2
输出
2
样例 2
输入
4
2 4
4 3
9 3
100 5
输出
2
样例 3
输入
5
3 1
8 1
7 3
0 3
4 2
输出
2

算法解析依据一般

考点：计算几何

数据规模 n ≤ 200000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 200000
  • 元素值域：X_i ≤ 1e9，L_i ≤ 1e9（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：计算几何

把几何关系转成坐标运算，用整数运算避免浮点误差。

思路框架（计算几何 通法 · 非本题专属）

  1. 把点、向量、线段用坐标表示。
  2. 几何判定（平行、垂直、共线、相交）尽量用叉积/点积的整数形式：叉积为 0 即共线。
  3. 距离用平方比较，避免开方带来的浮点误差。
  4. 面积用叉积（鞋带公式）计算。

实现要点：叉积 cross = x1*y2 - x2*y1；用它判断顺时针/逆时针和共线。

复杂度：时间 O(n) ~ O(n²) ｜ 空间 O(n)

该范式的通法易错点

  • 用浮点相等判断几何关系（应用整数叉积）。
  • 没考虑三点共线、重合等退化情况。

对照本题

  • 数据规模 n ≤ 200000，只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例

样例 1

  • 输入：5 / 2 3 / 7 1 / 5 1 / 8 3 / 0 2
  • 输出：2

样例 2

  • 输入：4 / 2 4 / 4 3 / 9 3 / 100 5
  • 输出：2

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：贝壳找房2023届校招前端类试卷。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解