Задачи
Супермногоугольники
Супермногоугольники
На плоскости задано \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{30}) супермногоугольников (без пересечений и самопересечений). Каждый супермногоугольник задаётся координатами своих \textbf{K_i} (\textbf{3} ≤ \textbf{K_i} ≤ \textbf{30}, \textbf{1} ≤ \textbf{i} ≤ \textbf{N}) вершин в порядке обхода против часовой стрелки. Все координаты --- целые числа из диапазона \textbf{-32000..32000}. Требуется соединить супермногоугольники \textbf{М} отрезками так, чтобы:
\begin{enumerate}
\item Oтрезок соединяет только пару супермногоугольников.
\item Суммарная длина отрезков была минимальна.
\end{enumerate}
Между любыми двумя супермногоугольниками должен существовать путь (последовательность некоторых отрезков и частей границ супермногоугольников).
\InputFile
В первой строке число \textbf{N}. В следующих \textbf{N} строках. Число \textbf{K_i} и \textbf{K_i} пар чисел -- координаты вершин.
\OutputFile
В первой строке сумма длин найденных отрезков с точностью \textbf{10^\{-3\}}.
Входные данные #1
2 3 1 0 2 0 1 1 4 6 5 7 5 7 6 6 6
Выходные данные #1
6.364