22143번 - Гоночная трасса 스페셜 저지다국어

문제

В уездном городе N построили новую гоночную трассу. Трасса полностью готова к эксплуатации, необходимо лишь зарегистрировать ее во Всемирном Реестре Гоночных Трасс, но для этого необходимо выяснить ее протяженность.

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

Протяженностью трассы, согласно правилам Всемирного Реестра Гоночных Трасс, является длина кратчайшей траектории движения по трассе.

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

Ниже приведены рисунки гоночных трасс из примеров.

입력

Первая строка содержит единственное целое число n (3 ≤ n ≤ 258) — число звеньев ломаной внутреннего края трассы. Далее следуют n строк, содержащие пары чисел x_i^inner и y_i^inner (−1000 ≤ x_i^inner, y_i^inner ≤ 1000) — вершины ломаной внутреннего края трассы.

Следующая строка содержит единственное целое число m (3 ≤ m ≤ 258) — число звеньев ломаной внешнего края трассы. Далее следуют m строк, содержащие пары чисел x_i^outer и y_i^outer (−1000 ≤ x_i^outer, y_i^outer ≤ 1000) — вершины ломаной внешнего края трассы.

Ломаные не имеют общих точек и заданы в порядке обхода против часовой стрелки.

출력

В единственной строке выведите одно число — протяженность трассы. Ответ должен иметь относительную или абсолютную погрешность не более 10⁻⁶.

제한

힌트