题目内容

小美正在学习聚类算法，请你帮助她实现单链接层次聚类（$Hierarchical$ $Agglomerative$ $Clustering$, $HAC$, $Single-linkage$）。

你需要在仅使用 $numpy / pandas / scikit-learn$ 的前提下，将 $n$ 个二维点合并到指定簇数 $C$，并为原始每个点输出簇编号。

1. 距离定义

   $$d((x_1,y_1),(x_2,y_2)) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$

2. 初始化

   • 每个点自成一簇；簇的成员索引集合为 {$idx$}（$idx$ 为输入顺序下标）

3. 迭代合并（直到簇数=C） i. 计算簇间距离 - 对任意两簇 $A、B$：$D(A,B) = \min_{p \in A, q \in B} d(p,q)$ ii. 确定要合并的簇对 - 找到最小距离 $D_{min}$ 的所有簇对集合 $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 \cup B$ - 重复步骤 i-iii，直到簇数 $=C$

4. 簇编号映射（输出一致性） 合并结束后得到 $C$ 个簇 {$G_0, ..., G_{C-1}$}。 i. 计算各簇质心 $x, y$ 坐标 ii. 按 $x,y$ 升序排序 $→$ 顺序 {$H_0, ..., H_{C-1}$} - 若质心 $x$ 相等（$|\Delta x| < 1e-12$），再比质心 $y$； - 若仍相等，再比簇内最小索引 iii. 最终编号 $H_0 \to 0, H_1 \to 1, ...$

输入描述

单行JSON

{
 "C": 2,          // 目标簇数 (2 ≤ C ≤ n ≤ 100)
 "points": [[x1, y1],
         [x2, y2]
       ...]                // 原始顺序固定
}

• 所有坐标为浮点数/整数
• 无缺失值，无空行

输出描述

• 单行 $JSON$ 数组，长度 $= n$
• 第 $i$ 个元素 $=$ 输入中第 $i$ 个点所属簇编号
• 例：$[0, 0, 1, 1]$

补充说明

1. 为了确保通过测试用例，仅允许使用 $numpy / pandas / scikit-learn$。
2. 若是使用 $sklearn$ 库而非 $numpy$ 自定义实现，则调用 $sklearn.cluster.AgglomerativeClustering(linkage='single')$，需按照本题映射规则输出。

样例1

输入

{"C":2,"points":[[0,0],[0,1],[10,10],[10,11]]}

输出

[0, 0, 1, 1]