Автор: | Московская городская олимпиада по информатике 2003/04 г. | Ограничение времени: | 5 сек | |
Входной файл: | f.in | Ограничение памяти: | 200 Мб | |
Выходной файл: | f.out |
На клеточном поле введена система координат так, что центр координат находится в точке пересечения линий сетки и оси направлены вдоль линий сетки.
На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:
Ребенок хочет сжечь фигуру. При этом он может поджечь ее в одной точке, имеющей целочисленные координаты (например, в точке A на рисунке поджигать фигуру нельзя, а в точках B и C — можно).
Известно, что огонь распространяется вдоль спички равномерно (но по каждой спичке — со своей скоростью). Спичка может гореть в нескольких местах (например, когда она загорается с двух концов; или когда в середине диагональной спички огонь перекидывается с одной спички на другую — огонь расползается по вновь подожженной спичке в обе стороны).
Напишите программу, которая определит, в какой точке нужно поджечь фигуру, чтобы она сгорела за минимальное время.
№ | Входной файл (f.in ) |
Выходной файл (f.out ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|