← 返回题目列表

Codeforces · 119/E

E. 另类现实

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

在 3000 年,在平行现实中旅行已经成为一件例行公事。然而,人们必须考虑到,这样的旅行是非常危险的,因为你事先永远不知道你会去哪里......

例如,小瓦西亚发现自己处于游戏现实中,现在他必须成功完成一款非常奇怪的游戏的所有关卡才能回来。游戏现实是一个三维空间,其中有 n 个点。游戏有 m 个级别,在第 i 个级别开始时,玩家位于穿过原点的某个平面 Qi 处。在每个关卡中,Vasya 都必须使用特殊的机器人来构建并激活 n 个半径相等、中心位于给定点的强大能量球。玩家自己选择球体的半径。玩家需要花费R单位的金钱来建造半径等于R的球体(因此,可以免费建造半径为零的球体)。此外,每关一次,玩家都可以选择空间中的任意点,并从那里释放垂直于 Qi 平面的激光射线(此操作无需任何成本)。光线可以直接射向平面,也可以从平面射出。与射线至少共享一个点的球体将立即被激活。如果玩家已成功激活所有球体,则该关卡被视为已完成。请注意,所有 m 个级别的球体中心都是相同的,但球体不会保留:玩家应该在每个新级别上重新构建它们。

帮助 Vasya 找出足以完成每个级别的最低金额。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 900, 1 ≤ m ≤ 100) — 能量球的数量和游戏中对应的关卡数量。

以下 n 行每行包含三个整数 xi, yi, zi (0 ≤ xi, yi, zi ≤ 104) — 第 i 个球体中心的坐标。假设这些点在整个游戏过程中不会改变其位置。

然后是 m 行,每行包含三个整数 ai, bi, ci (0 ≤ ai, bi, ci ≤ 100, ai2 + bi2 + ci2 > 0)。这些数字是平面 Qi (aix + biy + ciz = 0) 方程中的系数,其中玩家位于第 i 层的开头。

输出

打印 m 个数字,每行一个:第 i 行应包含完成第 i 级所需的最小金额。绝对或相对误差不应超过10-6。

示例

输入 #1

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

输出 #1

0.7071067812

输入 #2

5 3
0 1 0
1 0 1
1 2 1
2 0 1
1 3 0
1 1 1
1 2 3
3 0 3

输出 #2

1.6329931619
1.6366341768
1.5411035007

输入 #3

2 1
0 20 0
0 0 0
0 10 0

输出 #3

0.0000000000