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

题目描述

小红需要使用 K-Means 把 n 个三维点划分为 k 个簇。
取输入的前 k 个点作为编号 0 到 k-1 的初始质心。每轮先把每个点分配给欧氏距离最近的质心，距离相同时选择编号较小的簇；再用簇内点的坐标均值更新质心。若某簇为空，则该质心保持不变。
当所有质心的每个坐标变化量都小于 10^-6 ，或已经完成 100 轮时停止。输出最后一次分配得到的簇编号。

输入输出

输入描述
第一行输入 n,k 。接下来 n 行，每行输入一个点的三个浮点坐标。
保证 1 ≤ n ≤ 1000 ， 1 ≤ k ≤ n ，坐标范围为 [-100,100] 。
输出描述
输出 n 行，第 i 行是第 i 个点所属的簇编号。

样例共 2 组

样例 1 · 第三个点到两个初始质心等距，因此归入编号更小的簇 0。
输入
3 2
0.0 0.0 0.0
0.0 1.0 1.0
1.0 1.0 0.0
输出
0
1
0
样例 2 · 第三个点更接近质心 0。
输入
3 2
0.0 0.0 0.0
2.0 2.0 2.0
0.0 1.0 0.5
输出
0
1
0

算法解析依据一般

考点：计算几何

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

题目画像

  • 数据规模：n ≤ 1e3
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：计算几何

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 n ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 3 2 / 0.0 0.0 0.0 / 0.0 1.0 1.0 / 1.0 1.0 0.0 → 输出 0 / 1 / 0

第三个点到两个初始质心等距，因此归入编号更小的簇 0。

样例 2：输入 3 2 / 0.0 0.0 0.0 / 2.0 2.0 2.0 / 0.0 1.0 0.5 → 输出 0 / 1 / 0

第三个点更接近质心 0。

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

本题来源：2026年-华为-06月12号AI岗。

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