Коридор#5544
Музей зачиняється прямо зараз, і у вас є можливість оглянути лише один коридор. Під тиском часу ви вирішили не втрачати цю нагоду.
Коридор не містить жодних експонатів — сам коридор є експонатом. Якщо подивитися на нього зверху, він має дві протилежні стіни, кожна з яких утворює багатокутний ланцюг (багатокутний ланцюг — це послідовність вершин, з'єднаних відрізками). На плані коридору видно, що в кожному ланцюгу координати вершин розташовані в строго зростаючому порядку. Більше того, перша і остання вершини в такому порядку є єдиними точками, де дві стіни збігаються — це місце розташування входу і виходу.
Щоб уникнути охоронців, які збираються вас переслідувати, необхідно обчислити довжину найкоротшого шляху від входу до виходу.
Перший рядок містить кількість тестів . Далі йдуть самі тестів.
Перший рядок кожного тесту містить кількість вершин n_1 у верхньому багатокутному ланцюгу. Кожен з наступних n_1 рядків містить два цілі числа x_i, y_i (|x_i|, |y_i| \le 10^9) — координати -ої вершини ланцюга. Вершини перелічені в порядку зростання координати . Після опису верхнього ланцюга йде рядок зі значенням n_2, за яким слідує опис нижнього ланцюга. Можна вважати, що n_1 + n_2 \le 200\,000. Гарантується, що верхня стіна розташована вище нижньої по всій своїй довжині, за винятком кінців.
Для кожного тесту виведіть довжину найкоротшого шляху, що з'єднує кінці ланцюгів і розташований між двома багатокутними ланцюгами. Відповідь має бути точною з абсолютною похибкою не більше 10^{-3} або відносною похибкою не більше 10^{-9}.
Приклад 1