美团 · 计算几何 · 算法编程题
美团 计算几何 n ≤ 200000 时限 1 秒 / 256 MB

题目描述

在二维直角坐标系中有 n+1 个点（按输入顺序编号为 1 n+1 ），每个点的横、纵坐标均为整数。记原点为 (0,0) 。
将连接原点与编号 1 的线段围绕原点旋转一整圈。若在某一时刻，这条线段恰好经过某个点（即该点位于线段上），则称该点被“扫到”。
请计算：除编号 1 以外，被“扫到”的不同编号的点有多少个。

输入输出

输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤ T≤ 10^4) 代表数据组数，每组测试数据描述如下：
第一行输入一个整数 n(1≤ n≤ 2 × 10^5) ；
此后共 n+1 行，每行输入两个整数 x,y(1≤ x,y≤ 10^9) ，表示一个点的坐标，按输入顺序依次编号为 1,2,...,n+1 ；
除此之外，保证单个测试文件的 n 之和不超过 2 × 10^5 。
输出描述
对于每一组测试数据，新起一行。
输出一个整数，表示被“扫到”的不同编号点的数量（不计编号 1 ）。

样例共 1 组

样例 1
输入
2
3
3 4
1 1
5 12
4 3
3
2 2
3 3
1 2
2 3
输出
2
1

算法解析依据一般

考点：计算几何

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

题目画像

  • 数据规模：n ≤ 200000，T ≤ 1e4
  • 元素值域：x ≤ 1e9，y ≤ 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

  • 输入：2 / 3 / 3 4 / 1 1 / 5 12 / 4 3 / 3 / 2 2 / 3 3 / 1 2 / 2 3
  • 输出：2 / 1

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

本题来源：2026年春招-美团-测试岗-第二批笔试。

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