P13807 [CERC 2022] Constellations

占星家们对他们的星座运势预测进行了严谨的科学研究，发现他们的方法论并不能比随机更好地预测未来。他们没有反思自身，而是将责任归咎于星星和历史上星座的构造，认为这些导致了他们无法预测未来。现在他们正在尝试一种新的星座构造方式，希望借此恢复他们的预知能力。 他们需要你的帮助来实现他们的迭代星座创建系统。最初，每颗星星都代表一个独立的星座。在每一步中，你需要将距离最近的两个星座合并为一个。两个星座 $A$ 和 $B$ 之间的距离定义为它们各自所有星星两两之间的平方欧几里得距离的平均值： $$d(A, B) = \frac{1}{|A||B|} \sum_{a \in A} \sum_{b \in B} ||a - b||^2$$ 如果有多对星座之间的距离相同，则应优先合并较老的星座。当比较可以合并的两对星座时，首先比较它们之间的距离。如果距离相同，则比较这两对中较老星座的年龄。如果仍然相同，则比较较新星座的年龄。星座的年龄定义为其最后一次合并时的时间，对于单星星座则为该星星的年龄。输入中的星星按从最老到最年轻的顺序给出。

第一行包含一个整数 $N$，表示星星的数量。接下来的 $N$ 行，每行包含两个用空格分隔的整数 $X_i$ 和 $Y_i$，表示第 $i$ 颗星星的坐标。

每当按照描述的星座创建系统完成一次合并后，输出新创建星座的大小。共需输出 $N-1$ 行。

### 输入范围 - $2 \leq N \leq 2000$ - 对于所有 $1 \leq i \leq N$，$-1000 \leq X_i, Y_i \leq 1000$ - 所有 $(X_i, Y_i)$ 坐标都是唯一的，因为物理上不可能有两颗星星在同一个点。 由 ChatGPT 4.1 翻译