eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Формула 42

Формула 42

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Для проведения гран-при Флатландии планируется построить новую трассу Формулы 42. Был приглашен известный проектировщик трасс Герман Килькин, и он сделал чертежи трассы. Однако после начала строительства выяснилось, что с проектом есть небольшая проблема.

Трасса Формулы 42 представляет собой территорию, ограниченную с двух сторон барьерами. Каждый барьер представляет собой замкнутую ломаную, которая является границей выпуклого многоугольника. Внутренний барьер находится полностью внутри внешнего и не имеет с ним общих точек. Болид Формулы 42 представляет собой круг. Радиус круга не регламентирован, и считается, что соревнования получаются тем зрелищнее, чем больше радиус болида.

Проблема в проектом трассы заключается в том, что Герман изобразил на чертеже отдельно форму внешнего барьера и отдельно — форму внутреннего. При этом их взаимное расположение не указано. Теперь строители трассы могут выбрать произвольное взаимное расположение барьеров. Они хотят расположить барьеры таким образом, чтобы гонка получилась максимально зрелищной. Каждый из барьеров можно перемещать параллельным переносом, но нельзя поворачивать, отражать или другим образом изменять.

Требуется выбрать такое взаимное расположение барьеров, чтобы получившуюся трассу можно было использовать для гонки с максимальным размером гоночного болида. Трассу можно использовать с болидом радиуса r, если болид такого радиуса, находясь на трассе, может совершить полный круг вокруг внутреннего барьера. В процессе движения никакая точка болида не должна оказываться строго внутри внутреннего барьера или строго снаружи от внешнего барьрера. Касания барьеров разрешены. Формально: для точки P внутри замкнутого барьера существует такая непрерывная замкнутая кривая, что точка P лежит внутри этой кривой, и для любой точки этой кривой круг с радиусом r с центром в этой точке лежит внутри внешнего барьера и снаружи от внутреннего барьера, касания разрешаются.

Помогите разобраться с планом Германа и понять, для какого максимального радиуса гоночного болида возможно построить гоночную трассу в соответствии с имеющимися чертежами внешнего и внутреннего барьеров.

Входные данные

Содержат описание двух многоугольников, границы которых задают формы внешнего и внутреннего барьеров, соответственно.

В первой строке находится целое число n (3n100) - количество вершин в первом многоугольнике. В следующих n строках даны по два целых числа x[i] и y[i] (0x[i], y[i]1000) - координаты вершин первого многоугольника.

В следующей строке находится целое число m (3m100) - количество вершин во втором многоугольнике. В следующих m строках даны по два целых числа x[i]' и y[i]' - координаты вершин второго многоугольника (0x[i]', y[i]' ≤ 1000).

Вершины каждого многоугольника заданы в порядке обхода против часовой стрелки. Многоугольники является выпуклыми, никакие три вершины одного многоугольника не лежат на одной прямой. Гарантируется, что можно осуществить параллельный перенос многоугольников таким образом, что второй окажется строго внутри первого, и их границы не будут иметь общих точек.

Выходные данные

Выведите одно число - максимальный радиус болида. Ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает 10^(-6).

prb8719.gif

Пример

Входные данные #1
4
0 0
3 0
3 3
0 3
4
0 0
1 0
1 1
0 1
Выходные данные #1
0.500000000
Входные данные #2
4
0 0
3 0
3 3
0 3
3
0 0
2 1
1 2
Выходные данные #2
0.250000000
Источник 2018, XXVI Командный чемпионат школьников Санкт-Петербурга по программированию, 18 октября, Задача K