|
Remote Training on Programming
|
| Hello, Guest! Login or register. |
584. Триангуляция-2
|
| View Problem Statistics | Submit | Problem added Undefined |
|
Триангуляцией многоугольника называется разбиение многоугольника на треугольники, так чтобы диагонали, соединяющие вершины многоугольника, не пересекались. Минимальной триангуляцией называется такое разбиение многоугольника на треугольники, когда общая сумма диагоналей, указанных выше, была минимальной. Необходимо для данного многоугольника проверить, являются ли указанные диагонали многоугольника хордами минимальной триангуляции. Входные данные: в первой строке: 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 |
| View Problem Statistics | Submit | Author/source: |
| Educational Courses / | Data Structures and Algorithms / | Place for problems from students' projects / |
| 817. Сортировка слиянием | 584. | 583. 7 - Определения приращения |
| 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. |
| © Copyright VSTU, AVT, Nosov D.A. |