#P1990. Giveyouachance

Giveyouachance

蚂蚁在潜心研究宇宙规划(类似于城市规划),它准备申请这方面的工作。
简单来说宇宙里有很多工厂(每个工厂的位置都是独一无二的),每个工厂都有自己的生产线,蚂蚁已经调查出来他们生产线的能力了。
生产线能力用每天生产多少个产品以及每个产品的价值来表示(当然总价值越大,该生产线能力越大)。
蚂蚁发现这里所有的工厂原料来源都是相同的(蚂蚁心想:难道这些工厂都是用相同的原料?好吧,蚂蚁假设是的)
现在因为节能减排,宇宙总部决定只留下前四家总价值最大的工厂,然后建立两条光速索道和一个收费站。索道是两端无限长的直线,收费站是一个定点。
由于经费问题,这样的索道只能建立两条,并且一家工厂必须仅接上一条索道,蚂蚁从收费站到每个工厂的时间要相等且最小(不在索道上每一个距离单位需要一个时间单位,光速索道忽略在上面行走的时间)。
现在宇宙总部想知道所需的收费站的位置,并输出到各工厂的最小时间。
只有解决这个问题才可能有机会得到这份工作。于是它向你求助。

Input

第一行一个整数T表示测试数据的组数( T <= 100 )
每组数据第一行一个整数N表示N个工厂(4 <= N <= 1000)
接下来N行每行五个整数a b x y z表示该工厂每天生产a个产品,每个产品的价值为b,且该工厂位于(x,y,z)位置 (|a|,|b|,|x|,|y|,|z| <= 1000)

Output

一行一个数,表示最小时间

Sample Input

1
4
2 3 0 3 0
5 1 1 5 4
6 1 1 3 5
3 3 5 5 1

Sample Output

</p>
0.87

HINT

eps:1e-8
如果工厂产值一样,选取最先输入的工厂

Source