比赛场次	113
比赛名称	20111107
比赛状态	已结束比赛成绩
开始时间	2011-11-07 08:30:00
结束时间	2011-11-07 11:30:00
开放分组	全部用户
注释介绍

题目名称	燃烧
输入输出	`firez.in/out`
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试点数	10 简单对比

用户	结果	得分
Des.	AAAAAAAAAA	100
王者自由	AAAAAAAAAW	90
reamb	WWAWAAWWWA	40
lizhe	WWWWWWWAAW	20
临轩听雨ゐ	WWWWAWWWWW	10
风华正茂	WWWWWWWWWA	10
Czb。	WWWWAWWWWW	10
Truth.Cirno	WWWWAWWWWW	10
苏轼	C	0
Makazeu	WWWWWWWWWW	0
hello！	WWWWWWWWWW	0
magic	TTTTWTTTTT	0
血之侍卫	WWWWWWWWWW	0
Yeehok	WWWWWWWWWW	0
song	WWWWWWWWWW	0

燃烧

★★ 输入文件：firez.in 输出文件：firez.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

Tom 是调皮的孩子，特别喜欢玩火，现在他手上有若干根长度分别为 1 和 sqrt(2) 的木棍，还有一张不能燃烧的平板，他把平板划分成长度为 1 的单元格，并标上座标。然后按以下规则把平板上的木棍组成一个连通图：木棍的两端必须放在单元格的顶点上。即长度为 1 的木棍放在单元格的某一边上，长度为 sqrt(2) 的木棍放在单元格的对角线上。

Tom 的点火规则是，只能从木棍的两端点火，而不能从木棍的中间点火。如图，不能在 A 点点火，但在 C 点或 B 点点火都是允许的。点火后，火会沿着木棍向前燃烧（每根都有自己的燃烧速度），并能点燃与它相接的其它木棍。

任务：写一程序计算从哪里开始点火，使得燃烧的总时间最短，输出最短时间。

Input Data

输入文件第一行为一个正整数 N ，表示组成图形的木棍数目，后面共有 N 行，每行 5 个数： X1 Y1 X2 Y2 T , 其中（ X1 , Y1 ）和（ X2 , Y2 ）分别表示木棍两端的坐标， T 表示木棍燃烧时间，是指从木棍的某一端点火燃烧到别一端，燃完所需的时间。

Output Data

输出文件是一个保留 4 位小数的实数，表示所有木棍完全燃烧的最少时间。

约束 1 ≤n≤40

保证图形是连通的，所有的木棍长度都是 1 或 sqrt(2)，没有任何两根木棍重合 .

-200≤ X1, Y1, X2, Y2 ≤200; 0≤ T ≤ 10^7 .

如果你的输出结果与标准答案相差小于 0.001 ，则认为你的结果正确。

样例 1

firez.in

firez.out

解释

0 0 1 1 1

1.0000

从任一端点火都行，燃烧时间都是 1

样例 2

firez.in

firez.out

解释

0 0 0 1 1

1 0 0 1 10

0 0 1 0 1

0 0 1 1 1

2 2 1 1 1

3.2500

在 (0,0) 位置点火

木棍 1, 3 和 4 将被点燃，燃烧 0.5 分钟后，木棍 2 将被从中间点燃向两端燃烧，再过 0.5 分钟，木棍 1, 3, 4 将被完全燃烧，木棍 5 将被点燃并在 1 分钟后燃烧完 ( 比木棍 2 早燃完 ) 。

木棍 2 从中间向两端燃烧 0.5 分钟以后，变成两小段，每段的燃烧时间是 4.5 分钟。但因为此时两小段木棍的另一端也同时被点燃，燃烧速度变成原来的两倍，还需 2.25 分钟的燃烧时间，所以总时间： 1 + 2 . 25 = 3 . 25

样例 3

firez.in

firez.out

解释

1 1 1 2 10

1 2 2 2 10

1 1 2 2 50

35.0000

在 (1,2) 位置点火，木棍 (1 1, 1 2) 和 (1 2, 2 2) 将燃烧 10 分钟。 . 最后一根木棍在 10 分钟后从两端被点燃，燃烧时间为 25 分钟。