题目内容

在一项空间数据分析中，有 $n$ 个采样点，编号为 0, 1, $\ldots$, n-1，每个点具备唯一的二维坐标。需要将这些点合并成恰好 $C$ 个簇。

初始时，每个点自成一个簇。随后重复以下步骤，直到簇总数等于 $C$：

1. 对于任意两个簇 $A$ 与 $B$，定义它们的距离为：

   $$D(A,B)=\min_{p\in A,\,q\in B} d(p,q),$$

   其中 $d(p,q)$ 是两点之间的欧氏距离。

2. 找出所有距离最小的簇对。如果有多个这样的簇对，按以下规则确定合并目标：对于每一对簇，记其中包含的点的最小编号分别为 $a$ 和 $b$（设 $a<b$），构造有序对 $(a,b)$。比较所有这些有序对，选择字典序最小的那对。

3. 将选出的两个簇合并成一个新簇，其成员为原来两个簇中所有点的并集。

当簇的数量达到 $C$ 时停止合并。接下来为这 $C$ 个簇分配连续的编号 0, 1, $\ldots$, C-1。分配前先计算每个簇的中心，即其所有点坐标的算术平均。然后按以下优先级对簇进行升序排序：

• 第一关键字：中心的 $x$ 坐标；
• 若两个中心 $x$ 坐标之差的绝对值小于 $10^{-12}$，则比较 $y$ 坐标；
• 若 $x,y$ 皆无法区分，则比较簇内所含点的最小编号。

排序后，依序将编号 0 到 C-1 赋予各个簇。最终，你需要给出每个点所属簇的编号。

约束

• 点数 $n$ 满足 $2 \le C \le n \le 100$。
• 所有坐标的绝对值不超过 $10^6$，坐标值可以是整数或浮点数。

输入描述

输入只有一行，包含一个 JSON 字符串。该 JSON 对象包含两个字段："C" 为一个整数，表示最终需要保留的簇的个数；"points" 为一个二维数组，按输入顺序给出每个采样点的坐标，形如 [[x0,y0],[x1,y1],...]。所有坐标的绝对值均不超过 $10^6$。

输出描述

输出一行，包含一个 JSON 数组，其长度等于点数 $n$。数组的第 $i$ 个元素为输入中第 $i$ 个点最终所属簇的编号（编号从 0 开始且连续）。

样例1

输入

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

输出

[0, 0, 1]

说明

初始每个点自成一簇，计算所有簇对的欧氏距离：d(0,1)=2，d(0,2)=\sqrt{5}，d(1,2)=\sqrt{5}。最小距离为2，仅有一个簇对(0,1)，合并为$\{0,1\}$。 此时簇数为2，已达到$C$，停止合并。 计算各簇中心：$\{0,1\}$中心为$((0+2)/2,(0+0)/2)=(1,0)$；$\{2\}$中心为$(1,2)$。按$x$坐标升序：两者$x$均为1，差值的绝对值$0<10^{-12}$，因此比较$y$坐标，$0<2$，故$\{0,1\}$排在前面，获得编号0；$\{2\}$获得编号1。 点0、1属于簇0，点2属于簇1，输出[0,0,1]。

样例2

输入

{"C":2,"points":[[0,0],[2,0],[0,2],[2,2]]}

输出

[0, 0, 0, 1]

说明

初始4个点自成簇。两两距离：d(0,1)=2，d(0,2)=2，d(0,3)=2\sqrt{2}，d(1,2)=2\sqrt{2}，d(1,3)=2，d(2,3)=2。最小距离为2，涉及簇对(0,1)、(0,2)、(1,3)、(2,3)。 构造有序对$(a,b)$ ($a<b$)：$(0,1)$，$(0,2)$，$(1,3)$，$(2,3)$。字典序最小的是$(0,1)$，合并$\{0\}$与$\{1\}$，得$\{0,1\}$。 当前簇为$\{0,1\}$、$\{2\}$、$\{3\}$。重新计算距离：$D(\{0,1\},\{2\})=\min(d(0,2),d(1,2))=2$，$D(\{0,1\},\{3\})=\min(d(0,3),d(1,3))=2$，$D(\{2\},\{3\})=2$，再次全部相等。 对应的有序对：$\{0,1\}$最小编号为0，$\{2\}$最小编号为2得$(0,2)$；$\{0,1\}$与$\{3\}$得$(0,3)$；$\{2\}$与$\{3\}$得$(2,3)$。字典序最小为$(0,2)$，合并$\{0,1\}$与$\{2\}$，得$\{0,1,2\}$。 此时簇数为2等于$C$，停止合并。簇$\{0,1,2\}$中心为$(\frac{2}{3},\frac{2}{3})$，$\{3\}$中心为$(2,2)$。按$x$升序：$\frac{2}{3}<2$，故$\{0,1,2\}$编号0，$\{3\}$编号1。 点0、1、2属于簇0，点3属于簇1，输出[0,0,0,1]。

样例3

输入

{"C":3,"points":[[3,0],[0,3],[1,1]]}

输出

[2, 0, 1]

说明

$C=3$且$n=3$，初始簇数即为$C$，无需合并。 每个点自成一簇，中心即坐标：点0 $(3,0)$，点1 $(0,3)$，点2 $(1,1)$。 按中心的$x$坐标升序：点1的$x=0$最小，其次点2的$x=1$，点0的$x=3$最大。因此点1获得编号0，点2获得编号1，点0获得编号2。 还原为输入顺序：点0编号为2，点1编号为0，点2编号为1，输出[2,0,1]。