Language:

Remote Training on Programming

For authors:

About project

Hello, Guest! Login or register.

291. Triangulation

Time Limit:	1 seconds
Memory Limit:	64000KB
Points:	5

View Problem Statistics

Submit

Problem added Undefined

Найти минимальную триангуляцию выпуклого многоугольника, заданного координатами вершин, в порядке обхода их по часовой стрелке.

Триангуляцией многоугольника называется разбиение многоугольника на треугольники диагоналями, причем ни одна из диагоналей не пересекает ранее проведенную. Длина проведенных диагоналей должна быть минимальна среди всех возможных вариантов разбиения.

Входные данные

В первой строке количество вершин N (3<=N<=50), в следующих - пары координат вершин X_i и Y_i (целые числа), разделенные пробелом.

Выходные данные

Стоимость оптимальной триангуляции (округленная до целого)

Пример

Input	Output
4 90 117 197 98 251 164 152 177	90

Автор: Кунташев А.А.

View Problem Statistics

Submit

Author/source:

Sorted Problems /

Dynamic programming, recurrent relations /

873. Tower of Hanoi

291.

955. Кол-во R-разрядных чисел с суммой цифр, кратной K

870. Куча камней - 2 (дополненная)

Educational Courses /

Data Structures and Algorithms /

Student's Problems - old groups /

300. Shellsort

291.

We can all benefit by doing occasional "toy" programs, when artificial restrictions are set up, so that we are forced to push our abilities to the limit. The art of tackling miniproblems with all our energy will sharpen our talents for the real problems. Donald E. Knuth.

time generating 0.063 sec.