На клеточном поле введена система координат так, что центр координат находится в точке пересечения линий сетки и оси направлены вдоль линий сетки.
На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:
- Спички длины 1 выкладывались по сторонам клеток.
- Спички длины выкладывались по диагоналям клеток.
Ребенок хочет сжечь фигуру. При этом он может поджечь ее в одной точке, имеющей целочисленные координаты (например, в точке A на рисунке поджигать фигуру нельзя, а в точках B и C — можно).
Известно, что огонь распространяется вдоль спички равномерно (но по каждой спичке — со своей скоростью). Спичка может гореть в нескольких местах (например, когда она загорается с двух концов; или когда в середине диагональной спички огонь перекидывается с одной спички на другую — огонь расползается по вновь подожженной спичке в обе стороны).
Напишите программу, которая определит, в какой точке нужно поджечь фигуру, чтобы она сгорела за минимальное время.
Входные данные
Во входном файле записано сначала число N — количество спичек (1<N<40). Затем идет N пятерок чисел вида X
1, Y
1, X
2, Y
2, T, задающих координаты концов спички и время ее сгорания при условии, что она будет подожжена с одного конца (гарантируется, что каждая спичка имеет длину 1 или , все спички образуют связную фигуру, и положение никаких двух спичек не совпадает). Все координаты — целые числа, по модулю не превышающие 200, время сгорания — натуральное число, не превышающее 10
7.
Выходные данные
Выведите координаты целочисленной точки, в которой нужно поджечь фигуру, чтобы она сгорела за наименьшее время, а затем время, за которое в этом случае фигура сгорит. Время должно быть выведено с точностью не менее 2-х знаков после десятичной точки. Если решений несколько, выведите любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
0 0 1 1 1
|
0 0
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
|
0 0
3.25
|
|
3
|
3
1 1 1 2 10
1 2 2 2 10
1 1 2 2 50
|
2 2
35.00
|