|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
291. Триангуляция
|
| Статистика | Послать на проверку | Задачу добавил Неизвестный |
|
Найти минимальную триангуляцию выпуклого многоугольника, заданного координатами вершин в порядке обхода их по часовой стрелке. Триангуляцией многоугольника называется разбиение многоугольника на треугольники диагоналями, причем ни одна из диагоналей не пересекает ранее проведенную. Сумма длин проведенных диагоналей должна быть минимальна среди всех возможных вариантов разбиения. Входные данные В первой строке количество вершин N (3<=N<=50), в следующих - пары координат вершин Xi и Yi (целые числа), разделенные пробелом. Выходные данные Стоимость оптимальной триангуляции (округленная до целого) Пример
Автор: Кунташев А.А. |
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Задачи по темам / | Динамическое прогр-е, рекуррентные соотношения / |
| 657. Сумма цифр кратна K | 291. | 298. У магазина | 10. Упаковка | 68. Уравнение с пропущенными цифрами |
| Учебные курсы / | Алгоритмы и структуры данных / | Задачи из курсовиков - прошлые группы / |
| 300. Сортировка Шелла | 291. | 371. Уплотнение фибоначчиевой пирамиды |
| Задачи с соревнований и сборов / | Школьные олимпиады и курсы Вологодской области / | Импульс, смена 2019 / | Динамическое программирование / |
| 12. 12 - Быстрое питание | 291. |
| время генерации 0.094 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |