@Fylhtq1997

Пожалуйста напешите программу на С ++:
Дан выпуклый n угольник (заданный координатами своих вершин в порядке обхода). Его разрезают на треугольники диагоналями, для чего необходимо п -3 диагонали. Стоимостью разрезания назовем сумму длин всех использованных диагоналей. Найти минимальную стоимость разрезания
Спасибо!

Добавлено через 3 часа 17 минут
Алгоритм этой задачи такой, а как его написать на С++:
Решение: Будем считать, что вершины пронумерованы от 1 до n и идут по часовой стрелке. Пусть k, l - номера вершин, причем l>k. Через A(k,l) обозначим многоугольник, отрезаемый от нашего хордой k--l. (Эта хорда разрезает многоугольник на 2, один из которых включает сторону 1--n; через A(k,l) мы обозначаем другой.) Исходный многоугольник естественно обозначить A(1,n). При l=k+1 получается "двуугольник" с совпадающими сторонами.
Через a(k,l) обозначим стоимость разрезания многоугольника A(k,l) диагоналями на треугольники. Напишем рекуррентную формулу для a(k,l). При l=k+1 получается двуугольник, и мы полагаем a(k,l)=0. При l=k+2 получается треугольник, и в этом случае также a(k,l)=0. Пусть l > k+2. Хорда k--l является стороной многоугольника A(k,l) и, следовательно, стороной одного из треугольников, на которые он разрезан. Противоположной вершиной i этого треугольника может быть любая из вершин k+1,...,l-1, и минимальная стоимость разрезания может быть вычислена как
min {(длина хорды k--i)+(длина хорды i--l)+a(k,i)+a(i,l)}
по всем i=k+1,..., i=l-1. При этом надо учесть, что при q=p+1 хорда p--q - не хорда, а сторона, и ее длину надо считать равной 0 (по стороне разрез не проводится).
Составив таблицу для a(k,l) и заполняя ее в порядке возрастания числа вершин (равного l-k+1), мы получаем программу, использующую память порядка n*n и время порядка n*n*n (однократное применение рекуррентной формулы требует выбора минимума из не более чем n чисел).

0