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

NEERC 2011, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

J. Нелётная погода

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Все вылеты из аэропорта Кольцово отложены. Главный диспетчер заявил, что, пока над территорией аэропорта висит подозрительная грозовая туча, он не позволит ни одному борту подняться в воздух. Впрочем, он заверил пассажиров, что ветер сносит тучу со скоростью один метр в секунду и скоро небо над аэропортом очистится. Правда, о направлении ветра он ничего не сказал.
Один из пассажиров нашёл в интернете спутниковый снимок территории аэропорта, сделанный ровно минуту назад. По снимку можно точно определить положение тучи на тот момент времени. Точные координаты аэропорта тоже найти нетрудно. Хватит ли этой информации, чтобы вычислить минимальное время, через которое диспетчер может дать добро на вылет самолётов?

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

Тучу и территорию аэропорта на снимке можно приближённо считать невырожденными строго выпуклыми многоугольниками на плоскости. В первой строке записаны целые числа n и m — количество вершин в многоугольнике, задающем территорию аэропорта, и количество вершин в многоугольнике, задающем тучу (3 ≤ n, m ≤ 50 000). В следующих n строках записаны координаты территории аэропорта в порядке обхода против часовой стрелки. Далее в аналогичном формате задано положение тучи. Все координаты указаны в метрах и являются целыми числами, не превосходящими 108 по модулю. Гарантируется, что на снимке туча закрывает хотя бы одну точку внутренней области аэропорта.

Результат

Выведите единственное число — минимальное количество секунд, которое может пройти до того момента, когда ни одна точка территории аэропорта не будет находиться под тучей. Выведите ответ с абсолютной или относительной погрешностью не более 10−6. Если уже сейчас туча может не закрывать ни одну точку территории аэропорта, выведите 0.

Пример

исходные данныерезультат
4 4
400 400
600 400
600 600
400 600
0 0
1000 0
1000 1000
0 1000
540.0
Автор задачи: Даниил Айзенштейн
Источник задачи: NEERC 2011, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1894. Нелётная погода