問題文
这个世界是 3 为了用坐标来表示尺寸,即位置, (x, y, z) 和 3 号码为必填项。这次的维度比之前更高。 200 让我们思考一下次元世界。换句话说,一个点的坐标是 这意味着它被表示为 (x_1, x_2, ..., x_{200}) 和 200 数字。
现在,200 关于维度空间 来自 1 不同编号的点最多为 5,000 有 5,000 件。这些 考虑连接 5,000 点以满足以下条件。
- 通过重复移动到连接点,您可以从任意点到达任意其他点。
- 移动同一点时 2 如果您决定不再经过多次,交通方式将会改变。 1 如下确定。
换句话说,我们想要将这些点连接起来形成一棵树。
而且,作为一个竞赛问题,这似乎是一个承诺,但让我们考虑一下将其捆绑起来,以使成本尽可能低。在这里,2 两点 连接 (a_1, a_2, ..., a_{200}) 和 (b_1, b_2, ..., b_{200}) 的成本确定如下。
-
2 两点
使用以下公式定义
類似度
。 (这称为“余弦相似度”)
- 此时,2 连接两点的成本为 1 - 類似度 。即相似度越高,成本越低,相似度越低,成本越高。
总成本由连接点所需的成本总和决定。这时,创建一个程序,找到一种以尽可能低的成本喜结连理的方法。然而,没有必要将成本最小化;输出结的成本是 最小的 1.01 如果成本在两倍以内则接受 。 除以
入力
输入是按以下格式从标准输入给出的。
seed
- 1 行是一个整数 seed (1 ≦ seed ≦ 10^6) 。
实际点的坐标是 使用 seed 由伪随机数生成。所有点的坐标值为 -50,000 以上 50,000 下方和上方 从非 0 的整数中统一选择。具体来说,使用以下伪代码确定坐标值。
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 位无符号整数类型,
替换为= ,
与^ 进行按位异或 (XOR),
位左移<< ,
让>> 代表向右移位。
出力
只是 输出 4,999 行。每行都有 必须写 2 整数 p, q ,这是一个点 p 和点 代表连接 q 。
还在输出末尾包含换行符。
入力例1
1
出力例1
输出太大,无法列出,但这种情况的最小成本约为 3739.378294998 。
入力例2
2
出力例2
这种情况下的最低成本约为 3741.147062644 。