|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
584. Триангуляция-2
|
| Статистика | Послать на проверку | Задачу добавил Пахолков Сергей Александрович |
|
Триангуляцией многоугольника называется разбиение многоугольника на треугольники, так чтобы диагонали, соединяющие вершины многоугольника, не пересекались. Минимальной триангуляцией называется такое разбиение многоугольника на треугольники, когда общая сумма диагоналей, указанных выше, была минимальной. Необходимо для данного многоугольника проверить, являются ли указанные диагонали многоугольника хордами минимальной триангуляции. Входные данные: в первой строке: n - число вершин многоугольника, где 4<=n<=12. в следующих n-строках перечислены координаты каждой вершины, в порядке их обхода по часовой стрелке. далее вводится m-количество диагоналей. В следующих m-строк перечислены диагонали многоугольника, которые необходимо проверить. Диагональ представлена в виде индексов 2-х различных вершин многоугольника, начиная с нулевой. Выходные данные: Вывести YES, если указанные диагонали являются хордами минимальной триангуляции. В случае если указанные диагонали не являются хордами минимальной триангуляции или их количество недостадочно - вывести NO. Пример входных данных: 7 0 10 0 20 8 26 15 26 27 21 22 12 10 0 4 2 0 2 5 0 5 5 3 Пример выходных данных: YES |
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Учебные курсы / | Алгоритмы и структуры данных / | Сюда помещаем задачи из курсовиков! / |
| 817. Сортировка слиянием | 584. |
| время генерации 0.125 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |