P4955.第1题-HAC聚类器
题目内容
小美正在学习聚类算法，请你帮助她实现单链接层次聚类（Hierarchical Agglomerative Clustering, HAC, Single−linkage）。
你需要在仅使用 numpy/pandas/scikit−learn 的前提下，将 n 个二维点合并到指定簇数 C，并为原始每个点输出簇编号。
-
距离定义
d((x1,y1),(x2,y2))=(x1−x2)2+(y1−y2)2
-
初始化
- 每个点自成一簇；簇的成员索引集合为 {idx}（idx 为输入顺序下标）
-
迭代合并（直到簇数=C）
i. 计算簇间距离
- 对任意两簇 A、B：D(A,B)=minp∈A,q∈Bd(p,q)
ii. 确定要合并的簇对
- 找到最小距离 Dmin 的所有簇对集合 P
- 消除平局，依次比较：
a. 第一关键字：较小簇对(min A, min B)中的最小索引
b. 第二关键字：较大簇对(min A, min B)中的次小索引
- 说明：设 a=min(A),b=min(B) 并令 a<b，则关键字序列为 (a,b)。比如若簇对 (0,3) 与 (1,2) 距离相同，则比较 (0,3) 与 (1,2)，取 (0,3)
- 取数字序最小的簇对作为本轮合并目标
iii. 合并簇
- 新簇成员 = A∪B
- 重复步骤 i-iii，直到簇数 =C
-
簇编号映射（输出一致性）
合并结束后得到 C 个簇 {G0,...,GC−1}。
i. 计算各簇质心 x,y 坐标
ii. 按 x,y 升序排序 → 顺序 {H0,...,HC−1}
- 若质心 x 相等（∣Δx∣<1e−12），再比质心 y；
- 若仍相等，再比簇内最小索引
iii. 最终编号 H0→0,H1→1,...
输入描述
单行JSON
{
"C": 2, // 目标簇数 (2 ≤ C ≤ n ≤ 100)
"points": [[x1, y1],
[x2, y2]
...] // 原始顺序固定
}
输出描述
- 单行 JSON 数组，长度 =n
- 第 i 个元素 = 输入中第 i 个点所属簇编号
- 例：[0,0,1,1]
补充说明
- 为了确保通过测试用例，仅允许使用 numpy/pandas/scikit−learn。
- 若是使用 sklearn 库而非 numpy 自定义实现，则调用 sklearn.cluster.AgglomerativeClustering(linkage=′single′)，需按照本题映射规则输出。
样例1
输入
{"C":2,"points":[[0,0],[0,1],[10,10],[10,11]]}
输出
[0, 0, 1, 1]
