做用户分群、图像分割、测点归组这类任务时，“究竟该分成几组”往往事先说不准。K-Means 必须由人给定簇数 K；X-Means 在它外面套上一层 BIC（贝叶斯信息准则），让程序自己在候选区间里把 K 挑出来。

本题要求实现 X-Means：给定 N 个 d 维数据点以及簇数候选区间 [Kmin, Kmax]，自动选出最优簇数 K，并输出各簇的中心坐标和每个数据点的簇标签。

算法介绍

K-Means 基础

K-Means 是最经典的无监督聚类算法：把 N 个点划分成 K 个簇，使簇内误差平方和（SSE）尽可能小。

SSE 定义：

也就是把每个点到其所属簇中心的欧氏距离平方全部累加。

算法步骤：

1. 初始化：按确定性策略从数据中挑出 K 个点作为初始簇中心（见文末提示，不允许随机初始化）
2. 分配（Assign）：把每个点归到距离最近的簇中心
3. 更新（Update）：把每个簇的中心改成该簇内所有点的均值
4. 重复 2、3 两步，直到某一轮迭代结束后所有点的簇标签都不再变化（视为收敛），或迭代轮数达到 100 轮上限

BIC（贝叶斯信息准则）

BIC 用于在若干 K 值对应的聚类结果之间做选择，既衡量拟合程度，也衡量模型复杂度：

参数说明：

理解要点：

• BIC 越小越好
• 第一项 $n\cdot\ln\left(\frac{SSE}{n}\right)$ 刻画拟合误差 —— SSE 越小越好
• 第二项 $p\cdot\ln(n)$ 是复杂度惩罚 —— 簇数越多，惩罚越重
• 簇数变多能压低 SSE，同时抬高惩罚，BIC 在两者之间取平衡

注意事项：

• 若 K-Means 收敛后簇中心重合而被合并，K 取合并后的实际簇数，而不是枚举时传入的 K
• 所有点重合导致 SSE=0 时，用 ε=1e-8 兜住 log(0)
• 若多个 K 算出的 BIC 相同，取其中最小的 K 作为最终结果

X-Means 算法流程

X-Means 的核心是枚举 + BIC 选优：

输入：数据集 X，簇数区间 [Kmin, Kmax]

对 K = Kmin, Kmin+1, ..., Kmax
    调用 KMeans(X, K)，得到 centers, labels, SSE
    合并重合的中心，得到实际的 centers, labels, k_actual
    计算 BIC = n·ln((SSE + 1e-8)/n) + k_actual·(d+1)·ln(n)
选取 BIC 最小的 K 对应的聚类结果作为最终输出

数据范围

• $1\leq N\leq 2000$
• $1\leq d\leq 10$
• 坐标绝对值不超过 $10^3$
• 保证 $1\leq K_{\min}\leq K_{\max}\leq N$

解答要求

时间限制：C/C++ 1000ms，其他语言 2000ms

内存限制：C/C++ 512MB，其他语言 1024MB

输入

• 第一行是两个整数 N 和 d，分别表示数据点个数与每个点的维度
• 接下来 N 行，每行 d 个浮点数，描述一个数据点的坐标
• 最后一行是两个整数 $K_{\min}$ 和 $K_{\max}$，表示允许的最小簇数与最大簇数，保证 $1\leq K_{\min}\leq K_{\max}\leq N$

输出

• 第一行输出一个整数 K，表示算法最终确定的簇数
• 随后 K 行，每行 d 个浮点数，表示各簇的中心坐标（保留小数点后 2 位）
• 最后一行包含 N 个整数（取值 0 到 K-1），按输入顺序表示每个点所属的簇
• 若无法进行聚类，则输出 0

样例1

输入

12 2
1.0 1.0
15.0 12.0
7.0 6.0
2.0 1.0
8.0 6.0
17.0 12.0
1.0 2.0
7.0 7.0
15.0 14.0
2.0 2.0
17.0 14.0
8.0 7.0
1 5

输出

3
1.50 1.50
7.50 6.50
16.00 13.00
0 2 1 0 1 2 0 1 2 0 2 1

解释：12 个二维点明显聚成三小堆，每堆 4 个点，分别围绕 (1.5,1.5)、(7.5,6.5)、(16,13)，堆内距离远小于堆间距离。把 K 从 1 枚举到 5，对应 BIC 依次为 56.29、43.86、22.36、29.13、32.90，K=3 时最小，所以最终簇数为 3。三个簇按中心坐标的字典序升序编号：0 号 (1.50,1.50)、1 号 (7.50,6.50)、2 号 (16.00,13.00)。再按输入顺序逐点判定：(1,1) 属于 0 号簇，(15,12) 属于 2 号簇，(7,6) 属于 1 号簇……得到最后一行标签。

样例2

输入

8 2
4.0 2.0
20.0 10.0
5.0 2.0
22.0 10.0
4.0 3.0
20.0 12.0
5.0 3.0
22.0 12.0
1 3

输出

2
4.50 2.50
21.00 11.00
0 1 0 1 0 1 0 1

解释：8 个二维点分成左右两堆，各 4 个点。左堆 (4,2)、(5,2)、(4,3)、(5,3) 的均值为 (4.50,2.50)，右堆 (20,10)、(22,10)、(20,12)、(22,12) 的均值为 (21.00,11.00)，两堆之间的距离远大于堆内距离。K 取 1、2、3 时 BIC 分别为 42.00、14.26、19.95，K=2 时最小，所以最终簇数为 2。按中心字典序编号后，左堆为 0 号、右堆为 1 号，最后一行按输入顺序交替给出 0、1 标签。

提示