Разбиение выпуклого N-угольника

Дан выпуклый N-угольник, заданный координатами своих вершин в порядке обхода. Он разрезается N-2 диагоналями на треугольники. Стоимость разрезания определяется суммой длин всех использованных диагоналей. Найти разрез минимальной стоимости.

Идея решения разбирается с использованием следующего рисунка.

Обозначим через S[k,l] стоимость разрезания многоугольника A[k,l] диагоналями на треугольники. При l=k+1 или k+2 S[k,l]=0, следовательно, l>k+2. Вершина с номером i, i изменяется от k+1 до l-1, определяет какое-то разрезание многоугольника A[k,l]. Cтоимость разрезания определим как:

S[k,l]=min{длина диагонали <k,i>+длина диагонали <i,l>+S[k,i]+S[i,l]}. При этом следует учитывать, что при i=k+1 диагональ <k,i> является стороной многоугольника и ее длина считается равной нулю.

Пример(N=6).

Дата добавления: 2014-11-28