eolymp
bolt
Try our new interface for solving problems
Məsələlər

Вокруг трека

Вокруг трека

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Чтобы сравнить гоночные трассы, мы хотим вычислить их длину. Трасса является строго двумерной (без возвышения). Она описывается двумя простыми многоугольниками, один из которых полностью содержится внутри другого. Трек - это область между этими двумя многоугольниками. Определим длину трека как минимальное расстояние, которое нужно преодолеть для завершения круга. Это может означать движение по самому краю трека и произвольно резкие повороты.

prb7851.gif

Иллюстрация теста номер 3 вместе с кратчайшим маршрутом вокруг трека (пунктирная линия).

Giriş verilənləri

Состоит из:

  • строка из числа n (3n50) - количество вершин во внутреннем многоугольнике;

  • n строк, i-ая из которых содержит два целых числа x[i] и y[i] (5 000x[i], y[i]5 000) - координаты i-ой вершины внутреннего многоугольника;

  • строка из числа m (3m50) - количество вершин во внешнем многоугольнике;

  • m строк, i-ая из которых содержит два целых числа x[i] и y[i] (5 000x[i], y[i]5 000) - координаты i-ой вершины внешнего многоугольника.

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

Çıxış verilənləri

Выведите одну строку с одним действительным числом: длиной дорожки. Ответ должен иметь абсолютную или относительную ошибку не более 10^(-6).

Nümunə

Giriş verilənləri #1
3
1 1
2 1
1 2
3
0 0
4 0
0 4
Çıxış verilənləri #1
3.41421356237309
Giriş verilənləri #2
5
1 1
5 1
5 5
3 3
1 5
4
0 0
6 0
6 6
0 6
Çıxış verilənləri #2
16
Giriş verilənləri #3
5
1 1
5 1
5 5
3 3
1 5
5
0 0
6 0
6 6
3 4
0 6
Çıxış verilənləri #3
16.4721359549996
Mənbə 2014 ACM North Western European Regional Contest (NWERC), Ноябрь 30, Задача A