Задача F. Юный поджигатель ≡

Автор:Московская городская олимпиада по информатике 2003/04 г.   Ограничение времени:5 сек
Входной файл:f.in   Ограничение памяти:200 Мб
Выходной файл:f.out  

Условие

На клеточном поле введена система координат так, что центр координат находится в точке пересечения линий сетки и оси направлены вдоль линий сетки.

На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:

Ребенок хочет сжечь фигуру. При этом он может поджечь ее в одной точке, имеющей целочисленные координаты (например, в точке A на рисунке поджигать фигуру нельзя, а в точках B и C — можно).

Известно, что огонь распространяется вдоль спички равномерно (но по каждой спичке — со своей скоростью). Спичка может гореть в нескольких местах (например, когда она загорается с двух концов; или когда в середине диагональной спички огонь перекидывается с одной спички на другую — огонь расползается по вновь подожженной спичке в обе стороны).

Напишите программу, которая определит, в какой точке нужно поджечь фигуру, чтобы она сгорела за минимальное время.

Формат входного файла

Во входном файле записано сначала число N - количество спичек. Затем идет N пятерок чисел вида X1, Y1, X2, Y2, T, задающих координаты концов спички и время ее сгорания при условии, что она будет подожжена с одного конца (гарантируется, что каждая спичка имеет длину 1 или sqrt(2), все спички образуют связную фигуру, и положение никаких двух спичек не совпадает).

Формат выходного файла

Выведите минимальное время сгорания фигуры. Время должно быть выведено с точностью не менее 2-х знаков после десятичной точки. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 40
Все координаты — целые числа, по модулю не превышающие 200, время сгорания — натуральное число, не превышающее 107.

Примеры тестов

№ Входной файл (f.in) Выходной файл (f.out)
1 
1
0 0 1 1 1
 
1.00
2 
5
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.25
3 
3
1 1 1 2 10
1 2 2 2 10
1 1 2 2 50

35.00
4 
16
0 0 0 1 1   -2 -1 -3 -1 1   -2 -1 -1 0 1   -2 -1 -1 -2 1
-1 0 0 0 1   0 3 1 3 1   1 3 2 2 1   2 2 2 1 1
2 1 1 0 1   2 0 1 1 1   2 0 1 0 1   2 1 1 1 1
0 0 1 0 1   0 1 -1 1 1   -1 1 -1 2 1   0 3 -1 2 1

4.50
0.076s 0.009s 15