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

Мост между островами

Мост между островами

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

Тысячи и тысячи лет назад существовало небольшое королевство в центре Тихого океана. Территория королевства состояла из двух островов. Из-за многолетнего влияния океанических течений острова приобрели форму выпуклых многоугольников. Король этого королевства захотел построить мост для соединения двух островов. С целью минимизации расходов на его строительство король просит Вас помочь найти минимальное расстояние между островами.

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

Состоят из нескольких тестов. Каждый тест начинается двумя целыми числами n и m (3n, m10000). Каждая из следующих n строк содержит пары координат, последовательно описывающих вершины одного многоугольника. Каждая из последующих m строк содержит пары координат, последовательно описывающих вершины второго многоугольника. Строка n = m = 0 сигнализирует об окончании входных данных. Все координаты находятся в интервале [-10000, 10000].

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

Для каждого теста вывести минимальное расстояние между островами с точностью до 0.001.

Пример

Входные данные #1
4 4
0.00000 0.00000
0.00000 1.00000
1.00000 1.00000
1.00000 0.00000
2.00000 0.00000
2.00000 1.00000
3.00000 1.00000
3.00000 0.00000
0 0
Выходные данные #1
1.000