#P1050. 星战

星战

题目背景

这次可以了,总司令。

题目描述

在这一轮的星际战争中,敌方在宇宙中建立了 nn 个据点,第 ii 个据点位于坐标 (xi,yi,zi)(x_i, y_i, z_i)。第 ii 个据点有一个脆弱值,记为 viv_i

你作为联合舰队的参谋长正在策划一次攻击。你将选择宇宙中一个坐标 (x,y,z)(x,y,z),放置一枚反物质炸弹。

反物质炸弹有一个威力参数 kk。如果要炸毁第 ii 个据点,那么就要求威力参数和据点 ii 的脆弱值乘积大于等于它们之间的曼哈顿距离,也就是说威力参数至少是

xix+yiy+zizvi.\frac{|x_i - x| + |y_i - y| + |z_i - z|}{v_i}.

注意到上式不一定是整数。炸弹的参数也不必要是整数。同时,炸弹的坐标也不必要是整数。

你希望炸弹可以炸毁全部的 nn 个据点。同时,威力参数越大,炸弹造价越高。因此你希望选择一个合适的坐标来放下炸弹,使得炸弹可以炸毁所有的据点,且炸弹的威力参数尽可能小。

据点的坐标可以重合,炸弹的坐标也可以与据点相同。

输入格式

第一行是一个整数,表示敌方据点数量 nn
接下来 nn 行,每行四个非负整数 xi,yi,zi,vix_i, y_i, z_i, v_i,描述一个敌方据点。

输出格式

输出一行一个实数,表示最小的符合要求的威力参数。

当你的输出与答案的绝对或相对误差不超过 10610^{-6} 时被认为正确。

样例

样例输入 1

4
0 0 0 1
1 2 0 1
3 4 0 1
2 1 0 1

样例输出 1

3.50000000

样例输入 / 输出 2

见下发文件 galaxy2.in/ans。该样例满足测试点 686 \sim 8 的限制。

样例输入 / 输出 3

见下发文件 galaxy3.in/ans。该样例满足测试点 161716 \sim 17 的限制。

数据范围与提示

本题共 2020 个测试点,每个测试点 55 分。

测试点编号 特殊性质
11 xi=yi=zi=0x _ i = y _ i = z _ i = 0
252 \sim 5 yi=zi=0y _ i = z _ i = 0
686 \sim 8 zi=0z _ i = 0
9109 \sim 10 n=2n = 2
111311 \sim 13 所有 viv _ i 相同
141514 \sim 15 n10n \le 10 且坐标不超过 55
161716 \sim 17 n1000n \le 1000
182018 \sim 20 n105n \le 10 ^ 5

对于所有数据,1n1051 \le n \le 10 ^ 50xi,yi,zi1060 \le x _ i, y _ i, z _ i \le 10 ^ 61vi1061 \le v _ i \le 10 ^ 6