Задачи
Коридор
Коридор
Музей закрывается прямо сейчас, и у Вас имеется один коридор, который можно посмотреть. Под давлением времени Вы решили не упустить возможность.
Коридор не содержит никаких экспонатов - сам коридор и есть экспонат. Если на него посмотреть сверху, то он имеет две противоположные стены, каждая из которых образует многоугольную цепь (многоугольная цепь - это последовательность вершин, соединенных отрезками). Посмотрев на план коридора, можно заметить, что в каждой цепи \textbf{x} координаты вершин находятся в (строго) возрастающем порядке. Более того, первая и последняя вершины в таком порядке являются единственными точками, где две стены совпадают - это место расположения входа и выхода.
\includegraphics{https://static.e-olymp.com/content/a7/a72ee5c6c5df02073893d0e47f36f9ea5631f02d.jpg}
Для того чтобы убежать от охранников, которые собираются преследовать Вас в течение некоторого времени, необходимо вычислить длину кратчайшего пути от входа к выходу.
\InputFile
Первая строка содержит количество тестов \textbf{T}. Далее следуют сами \textbf{T }тестов.
Первая строка каждого теста содержит количество вершин \textbf{n_1} в верхней многоугольной цепи. Каждая из следующих \textbf{n_1} строк содержит два целых числа \textbf{x_i}, \textbf{y_i} (|\textbf{x_i}|, |\textbf{y_i}| ≤ \textbf{10^9}) - координаты \textbf{i}-ой вершины цепи. Вершины перечислены в порядке возрастания \textbf{x} координаты. За описанием верхней цепи следует строка со значением \textbf{n_2}, за которой следует описание нижней цепи. Можно считать, что \textbf{n_1} + \textbf{n_2} ≤ \textbf{200 000}. Гарантируется, что верхняя стена лежит выше нижней по всей своей длине за исключением концов.
\OutputFile
Для каждого теста вывести длину кратчайшего пути, соединяющего концы цепей и расположенного между двумя многоугольными цепями. Вывод следует совершать с точностью до \textbf{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