华为 · 计算几何 · 算法编程题
华为 计算几何 时限 1 秒 / 256 MB

题目描述

在网络规划中，希望把若干二维站点拆分为多个子网，便于运维。给定期望子网数 N 和所有站点坐标，采用“二分 K-means”自顶向下的思路：从一个簇开始，每次只把当前 SSE（簇内点到簇心的平方和）最大的簇再二分为两个簇，直到簇数达到 N。二分时使用标准 K=2 的 K-means：初始两个簇心选该簇中 x 坐标最小点与 x 坐标最大点（如有并列，按 y 再按输入次序打破并列），迭代更新“按欧氏距离最近分配 + 以簇内平均坐标为新簇心”，当簇心总移动量均小于 1e-6 或迭代满 1000 次即认为收敛；若出现某一类空簇，则保持该簇心不变继续迭代。每次二分后输出当前所有簇的规模（站点数），按降序排列；共输出 N−1 行。

输入输出

输入描述
第一行：N（目标簇数，整数）
第二行：M（站点数，整数）
接下来 M 行：每行两个整数 x y（0≤x,y≤1000）
输出描述
共输出 N−1 行。第 k 行为完成第 k 次二分后的各簇规模（降序），以空格分隔

样例共 1 组

样例 1 · 首次把点大致按中间位置分成 {0,1} 与 {10,11,12}，规模为 2 与 3；第二次优先二分规模更大且 SSE 更大的簇 {10,11,12} 为 {10} 与 {11,12}，此时三个簇规模降序为 2 2 1。
输入
3
5
0 0
1 0
10 0
11 0
12 0
输出
3 2
2 2 1

算法解析依据一般

考点：计算几何

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 元素值域：x ≤ 1e3，y ≤ 1e3（注意整数类型选择，避免溢出）
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：计算几何

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 元素值域最大到 1e3 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 3 / 5 / 0 0 / 1 0 / 10 0 / 11 0 / 12 0 → 输出 3 2 / 2 2 1

首次把点大致按中间位置分成 {0,1} 与 {10,11,12}，规模为 2 与 3；第二次优先二分规模更大且 SSE 更大的簇 {10,11,12} 为 {10} 与 {11,12}，此时三个簇规模降序为 2 2 1。

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

本题来源：2025年秋招-华为-10月15号AI岗。

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