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

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

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

A. Гонки на карах

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Падме: У этих торговцев барахлом должны быть какие-то слабости.
Шми: Тотализатор. Всё здесь вертится вокруг этих ужасных гонок.
Квай-Гон: Гонки на карах. Их алчность может сыграть нам на руку.
Получив повреждения в бою, корабль королевы Амидалы был вынужден приземлиться на жаркой планете под названием Татуин. Квай-Гон Джинн отправился в город за запчастями для починки корабля. Но для покупки деталей требуется местная валюта, которой у джедая нет.
В лавке запчастей Квай-Гон встретил 9-летнего мальчика Энакина Скайуокера. Он с самого рождения жил на этой планете вместе со своей матерью Шми Скайуокер. Энакин давно мечтал принять участие в опасных гонках на карах, и даже сам собрал гоночный кар. Квай-Гон решил, что он поможет мальчику принять участие в соревнованиях. Он также договорился с рабовладельцем Уотто, что в случае победы Энакина джедаи получат запчасти, а мальчик — свободу. Осталось определить, каковы шансы Энакина на победу.
Трасса для гонок проложена вдоль оси Oy и ограничена двумя ломаными линиями слева и справа. Кары участников представляют собой горизонтальные отрезки. Кары могут двигаться в любом направлении и даже задевать границы трассы. Но при этом они всегда должны оставаться горизонтальными и находиться между ломаными.
Сложность в преодолении дистанции добавляют столбики с камерами, которые ни в коем случае нельзя сбивать. Столбики представлены материальными точками и могут находиться как на трассе, так и за её пределами. Касания столбиков концами отрезка проходят незаметно как для кара, так и для столбиков. Любой другой контакт недопустим.
Началу трассы соответствует минимальная y-координата вершин ломаных, финишу — максимальная. Изначально кар может располагаться в любом месте на уровне старта. Кар финиширует, если он добрался до уровня финиша. Помогите Квай-Гону определить максимально возможную ширину кара, способного финишировать.

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

В первой строке находится целое число n — количество вершин в левой ломаной. В i-ой из следующих n строк перечислены пары чисел xi и yi — координаты очередной вершины. Далее число m и ещё m строк с координатами правой ломаной. После этого задано целое число q и q строк с координатами столбиков. 2 ≤ n, m ≤ 105, 0 ≤ q ≤ 105, координаты всех точек целые и по модулю не превышают 109. Координаты вершин в каждой ломаной даны по увеличению y координаты, координаты столбиков — по неубыванию y координаты. Гарантируется, что ломаные не пересекаются, не касаются, и y-координаты как первых, так и последних вершин совпадают.

Результат

Выведите ответ с абсолютной или относительной погрешностью 10−6.

Пример

исходные данныерезультат
2
0 0
5 10
3
5 0
10 5
10 10
1
6 5
4.0
Автор задачи: Денис Дублённых (подготовка — Егор Щелконогов)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1990. Гонки на карах