Задача №1908. Оптимальная триангуляция - 1
Триангуляцией \(N\)-угольника называется набор из \(N\)-3 непересекающихся (кроме как в вершинах многоугольника) диагоналей, разбивающих \(N\)-угольник на \(N\)-2 треугольника.
Для заданного выпуклого \(N\)-угольника найдите триангуляцию, у которой сумма длин диагоналей, входящих в триангуляцию, минимальна.
Входные данные
Первая строка входных данных содержит целое число \(N\) (3≤\(N\)≤100) - количество вершин в многоугольнике. Далее идет \(N\) пар целых чисел \(x_i\), \(y_i\), не превосходящих 10000 по абсолютной величине - координаты выпуклого \(N\)-угольника в порядке обхода.
Выходные данные
Выведите одно действительное число - минимальную суммарную длину диагоналей триангуляции с точностью не менее 6 знаков.
Примеры
Входные данные
4 0 0 0 1 1 1 1 0
Выходные данные
1.41421356237
Сдать: для сдачи задач необходимо войти в систему