|
Найти минимальную триангуляцию выпуклого многоугольника, заданного
координатами вершин в порядке обхода их по часовой стрелке.
Триангуляцией многоугольника называется разбиение многоугольника на
треугольники диагоналями, причем ни одна из диагоналей не пересекает ранее
проведенную. Сумма длин проведенных диагоналей должна быть минимальна среди всех
возможных вариантов разбиения.
Входные данные
В первой строке количество вершин N (3<=N<=50), в следующих - пары
координат вершин Xi и Yi (целые числа), разделенные
пробелом.
Выходные данные
Стоимость оптимальной триангуляции (округленная
до целого)
Пример
| Input | Output |
|---|
4
90 117
197 98
251 164
152 177 | 91 |
Автор: Кунташев А.А.
| 