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 << 11)
    x = y
    y = z
    z = w
    w = (w ^ (w >> 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 自动生成