Внимание, внимание, говорит Москва, работают все радиостанции… Передаём экстренное сообщение.
Сегодня состоятся последние ходовые испытания нового супертанкера, флагмана отечественного наливного флота «Нефтяник». Впервые в мировой практике будет продемонстрирована новая разработка наших учёных — система «Лоцман», позволяющая оптимально управлять кораблем без участия человека в акватории прямоугольной гавани. Корабль (а ведь все корабли имеют треугольную форму) умеет перемещаться по кратчайшему расстоянию из заданного начального положения в конечное между другими кораблями, стоящими на якоре в гавани. На «Нефтянике» было предусмотрено практически всё, что необходимо для безопасного испытания: и толстая стальная обшивка, и электронная система управления, и спутниковая связь с комплексом определения координат, и чуткий радар. Но в дело вмешался, как это обычно и бывает, человеческий фактор. Вовочка, сын командира корабля, тайком пробрался на секретный объект как раз перед презентацией, сел к бортовому компьютеру и решил скоротать время за любимой компьютерной игрой. В результате на компьютер проник вирус и испортил часть функций программы «Лоцман». Теперь корабль не может совершать повороты вокруг своей оси. Требуется составить программу, вычисляющую длину кратчайшего маршрута танкера к заданной точке.
Исходные данные
В первой строке записаны целые числа DX, DY — размеры гавани (0 < DX, DY < 108). Строки 2-4 содержат по два целых числа — координаты танкера (напоминаем, что корабль "Нефтяник", как и все остальные корабли, имеет треугольную форму). В строке 5 указана точка, куда должен в итоге попасть корабль (а именно, тот из его углов, координаты которого описаны во второй строке входа). В строке 6 записано целое число N (количество других кораблей в гавани, 0 ≤ N ≤ 40). Следующие 3N строк входа содержат координаты этих кораблей. Все координаты находятся в пределах гавани. Угол гавани является началом координат. Корабли не пересекаются.
Результат
должен содержать единственное число — минимальную длину маршрута, округлённую до трёх знаков после десятичной точки, либо значение −1, если "Нефтянику" из-за повреждения навигационной программы не удастся доплыть до цели.
Пример
исходные данные | результат |
---|
2003 2003
20 50
10 30
30 30
140 60
1
80 1000
100 20
60 20 | 146.569 |
Замечания
- Гавань — прямоугольник с координатами углов (0,0), (DX,0), (DX,DY), (0,DY).
- Выплывать за пределы гавани нельзя.
- Корабли могут касаться друг друга и границ гавани.
Автор задачи: Алексей Лахтин
Источник задачи: Чемпионат Уральского государственного университета, 25 октября 2003 года