Навколо треку#7851

Навколо треку

1 секунда

128 мегабайтів

Складна

Щоб порівняти гоночні траси, ми хочемо обчислити їхню довжину. Траса є строго двовимірною (без підвищення). Вона описується двома простими багатокутниками, один з яких повністю міститься всередині іншого. Трек - це область між цими двома багатокутниками. Визначимо довжину треку як мінімальну відстань, яку потрібно подолати для завершення кола. Це може означати рух по самому краю треку і довільно різкі повороти.

Ілюстрація тесту номер 3 разом з найкоротшим маршрутом навколо треку (пунктирна лінія).

Вхідні дані

Складається з:

рядка з числом $n$ ( $3 \leq n \leq 50$ 3 \le n \le 50) - кількість вершин у внутрішньому багатокутнику;
$n$ рядків, де $i$ -ий містить два цілих числа $x_{i}$ x_i і $y_{i}$ y_i ( $- 5000 \leq x_{i}, y_{i} \leq 5000$ -5000 \le x_i, y_i \le 5000) - координати $i$ -ої вершини внутрішнього багатокутника;
рядка з числом $m$ ( $3 \leq m \leq 50$ 3 \le m \le 50) - кількість вершин у зовнішньому багатокутнику;
$m$ рядків, де $i$ -ий містить два цілих числа $x_{i}$ x_i і $y_{i}$ y_i ( $- 5000 \leq x_{i}, y_{i} \leq 5000$ -5000 \le x_i, y_i \le 5000) - координати $i$ -ої вершини зовнішнього багатокутника.

Вершини обох багатокутників задані в порядку проти годинникової стрілки. Межі багатокутників не перетинаються і не торкаються одна одної.

Вихідні дані

Виведіть один рядок з одним дійсним числом: довжиною доріжки. Відповідь повинна мати абсолютну або відносну похибку не більше $1 0^{- 6}$ 10^{-6}.

Приклади

Приклад 1

Приклад 2

Приклад 3