Вокруг трека
Вокруг трека
Чтобы сравнить гоночные трассы, мы хотим вычислить их длину. Трасса является строго двумерной (без возвышения). Она описывается двумя простыми многоугольниками, один из которых полностью содержится внутри другого. Трек - это область между этими двумя многоугольниками. Определим длину трека как минимальное расстояние, которое нужно преодолеть для завершения круга. Это может означать движение по самому краю трека и произвольно резкие повороты.
Иллюстрация теста номер 3 вместе с кратчайшим маршрутом вокруг трека (пунктирная линия).
Giriş verilənləri
Состоит из:
строка из числа n (3 ≤ n ≤ 50) - количество вершин во внутреннем многоугольнике;
n строк, i-ая из которых содержит два целых числа
x[i]
иy[i]
(5 000 ≤x[i]
,y[i]
≤ 5 000) - координаты i-ой вершины внутреннего многоугольника;строка из числа m (3 ≤ m ≤ 50) - количество вершин во внешнем многоугольнике;
m строк, i-ая из которых содержит два целых числа
x[i]
иy[i]
(5 000 ≤x[i]
,y[i]
≤ 5 000) - координаты i-ой вершины внешнего многоугольника.
Вершины обоих многоугольников заданы в порядке против часовой стрелки. Границы многоугольников не пересекаются и не касаются друг друга.
Çıxış verilənləri
Выведите одну строку с одним действительным числом: длиной дорожки. Ответ должен иметь абсолютную или относительную ошибку не более 10^(-6)
.
Nümunə
3 1 1 2 1 1 2 3 0 0 4 0 0 4
3.41421356237309
5 1 1 5 1 5 5 3 3 1 5 4 0 0 6 0 6 6 0 6
16
5 1 1 5 1 5 5 3 3 1 5 5 0 0 6 0 6 6 3 4 0 6
16.4721359549996