← 返回题目列表

Codeforces · 44/D

D. 超光速引擎

中文机器翻译题面 查看原题

在一个遥远的星系里,有n颗有人居住的行星,编号为1到n。它们彼此相距很远,这就是为什么它们之间的通信非常困难,直到第一号行星上发明了超空间驱动器。这一重大事件一发生,n - 1 艘宇宙飞船就在 1 号行星上建造起来,这些飞船被送往其他行星来宣传这项革命性的发明。

这可能是自相矛盾的想法,但超空间被表示为简单的三维欧几里德空间。有人居住的行星可以被认为是其中的固定点,没有两点重合,也没有三点位于同一条直线上。带有超光引擎的飞船在两个行星之间的移动是沿着直线以恒定的速度进行的,所有飞船都是一样的。这就是为什么超空间中的距离以超年为单位来测量(一艘装有超光速引擎的飞船在 s 年中行驶了 s 超年的距离)。

当飞船到达一颗有人居住的星球时,该星球的居民会拆解它,用超光速引擎制造 n - 2 艘与它相同的飞船,并将它们发送到其他 n - 2 个行星(除了飞船抵达的那颗行星)。与从一个星球移动到另一个星球的时间相比,制造一艘新飞船的时间是如此之短,以至于可以忽略不计。新飞船与最初发送的飞船完全相同:它们沿着直线轨迹以相同的恒定速度移动,到达一颗行星后,执行完全相同的任务,即被分解以建造新的 n - 2 艘飞船,并将它们发送到除飞船所来自的行星之外的所有行星。因此,在银河系中传播重要消息的过程仍在继续。

然而,超光速推进器的创造者们过于匆忙地传播有关他们发明的消息,以至于他们没有完全研究当两艘飞船在超空间相撞时会发生什么。如果两艘移动的飞船发现自己位于同一点,就会引发巨大的力量爆炸,导致银河系的毁灭!

你的任务是找到从飞船从第一颗行星发射的那一刻起,银河系将继续存在的时间。

输入

第一行包含数字 n (3 ≤ n ≤ 5000) — 银河系中有人居住的行星数量。接下来的 n 行包含行星的整数坐标,格式为“xi yi zi”(- 104 ≤ xi, yi, zi ≤ 104)。

输出

打印单个数字 — 绝对或相对误差不超过 10 - 6 的任务的解。

示例

输入 #1

4
0 0 0
0 0 1
0 1 0
1 0 0

输出 #1

1.7071067812