AT_arc021_4 [ARC021D] だいたい最小全域木

在这个世界中，我们习惯用三维坐标 $(x, y, z)$ 来表示一个点的位置。而这次，我们要考虑一个更高维度的世界，也就是 200 维空间。在这样的空间中，一个点的坐标会被表示为 200 个数字 $(x_1, x_2, \ldots, x_{200})$。 在这个 200 维空间中，有 5,000 个编号从 1 到 5,000 的点。我们的任务是连接这些点，满足以下条件： - 从任何一个点出发，可以通过连接的点到达任意其他点。 - 在移动过程中，每条路径是唯一的，且没有重复经过同一个点的情况。 简单来说，就是要把这些点连接成一棵树。 和往常一样，我们希望在连接过程中，尽可能降低总的连接成本。两个点 $(a_1, a_2, \ldots, a_{200})$ 和 $(b_1, b_2, \ldots, b_{200})$ 之间的连接成本定义如下： - 两点的 **相似度** 通过以下公式计算（这就是所谓的“余弦相似度”）： $$ \text{相似度} = \frac{\sum_{i=1}^{200} a_i b_i}{\sqrt{\sum_{i=1}^{200} a_i^2} \cdot \sqrt{\sum_{i=1}^{200} b_i^2}} $$ - 连接两点的成本为 $1 - \text{相似度}$。因此，相似度越高，成本越低；相似度越低，成本越高。 总的连接成本是所有连接的成本之和。请编写一个程序，使得连接的总成本尽量低。不过，只要输出的连接方式的成本不超过最低成本的 1.01 倍，也算作通过。

输入使用以下格式从标准输入提供： > $ seed $ - 第一行是一个整数 $seed (1 \leq seed \leq 10^6)$。 实际点的坐标是用这个 $seed$ 初始化的伪随机数生成器来产生的。所有点的坐标值从 $-50,000$ 到 $50,000$ 范围的非零整数中均匀选出。具体而言，坐标生成的伪代码如下所示： ``` x = 123456789 y = 362436069 z = 521288629 w = seed for i = 1 to 5000 for j = 1 to 200 t = x ^ (x > 19)) ^ (t ^ (t >> 8)) v = w % 100000 - 50000 if v >= 0 then v = v + 1 (第 i 个点的第 j 个坐标值) = v ``` 其中 `seed` 是输入的 $seed$ 值。变量 `x`, `y`, `z`, `w`, `t` 均为 32 位无符号整数，`=` 表示赋值，`^` 表示按位异或，`` 表示右移。

需输出正好 4,999 行。每行包含两个整数 $p$ 和 $q$，表示连接点 $p$ 和点 $q$。 输出最后需要多加一个换行符。

### 样例说明 1 由于输出量庞大，这里省略具体样例输出。对于此样例，最小成本约为 3739.378294998。 ### 样例说明 2 对于此样例，最小成本约为 3741.147062644。 **本翻译由 AI 自动生成**