ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1271. Лоцман

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
Внимание, внимание, говорит Москва, работают все радиостанции… Передаём экстренное сообщение.
Сегодня состоятся последние ходовые испытания нового супертанкера, флагмана отечественного наливного флота «Нефтяник». Впервые в мировой практике будет продемонстрирована новая разработка наших учёных — система «Лоцман», позволяющая оптимально управлять кораблем без участия человека в акватории прямоугольной гавани. Корабль (а ведь все корабли имеют треугольную форму) умеет перемещаться по кратчайшему расстоянию из заданного начального положения в конечное между другими кораблями, стоящими на якоре в гавани. На «Нефтянике» было предусмотрено практически всё, что необходимо для безопасного испытания: и толстая стальная обшивка, и электронная система управления, и спутниковая связь с комплексом определения координат, и чуткий радар. Но в дело вмешался, как это обычно и бывает, человеческий фактор. Вовочка, сын командира корабля, тайком пробрался на секретный объект как раз перед презентацией, сел к бортовому компьютеру и решил скоротать время за любимой компьютерной игрой. В результате на компьютер проник вирус и испортил часть функций программы «Лоцман». Теперь корабль не может совершать повороты вокруг своей оси. Требуется составить программу, вычисляющую длину кратчайшего маршрута танкера к заданной точке.

Исходные данные

В первой строке записаны целые числа 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 года