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

Коридор

Коридор

Ліміт часу 3 секунди
Ліміт використання пам'яті 128 MiB

Музей закрывается прямо сейчас, и у Вас имеется один коридор, который можно посмотреть. Под давлением времени Вы решили не упустить возможность.

Коридор не содержит никаких экспонатов - сам коридор и есть экспонат. Если на него посмотреть сверху, то он имеет две противоположные стены, каждая из которых образует многоугольную цепь (многоугольная цепь - это последовательность вершин, соединенных отрезками). Посмотрев на план коридора, можно заметить, что в каждой цепи x координаты вершин находятся в (строго) возрастающем порядке. Более того, первая и последняя вершины в таком порядке являются единственными точками, где две стены совпадают - это место расположения входа и выхода.

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

Вхідні дані

Первая строка содержит количество тестов T. Далее следуют сами T тестов.

Первая строка каждого теста содержит количество вершин n_1 в верхней многоугольной цепи. Каждая из следующих n_1 строк содержит два целых числа x_i, y_i (|x_i|, |y_i| ≤ 10^9) - координаты i-ой вершины цепи. Вершины перечислены в порядке возрастания x координаты. За описанием верхней цепи следует строка со значением n_2, за которой следует описание нижней цепи. Можно считать, что n_1 + n_2200 000. Гарантируется, что верхняя стена лежит выше нижней по всей своей длине за исключением концов.

Вихідні дані

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

Приклад

Вхідні дані #1
1
5
0 0
2 2
4 -1
5 1
6 0
5
0 0
1 -1
2 1
4 -2
6 0
Вихідні дані #1
7.301
Джерело 2013 Petrozavodsk Winter Training Camp, Jagiellonian University Contest, Січень 25, Задача C