eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Триангуляция

Триангуляция

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

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

  • вершины каждого треугольника выбираются среди вершин исходного многоугольника;

  • каждый треугольник должен быть невырожденным;

  • каждый треугольник должен полностью содержаться в исходном многоугольнике;

  • внутренние области любых двух треугольников не пересекаются.

Вхідні дані

Первая строка содержит число N (3N5000) — количество вершин многоугольника. Далее N строк по два целых числа в каждой: x_i, y_i (-10000x_i, y_{i }≤ 10000) — координаты вершин многоугольника в порядке обхода против часовой стрелки. Гарантируется, что все точки различные. Гарантируется, что любая пара сторон имеет ровно одну общую точку, если стороны соседние, и ни одной в противном случае.

Вихідні дані

N-2 строки, каждая из которых содержит три различных целых числа: a_i, b_i и c_i (1a_i, b_i, c_{i }≤ N) — номера вершин исходного многоугольника, которые формируют i-ый треугольник. Вершины исходного многоугольника нумеруются начиная с 1 в порядке появления во входных данных.

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

Приклад

Вхідні дані #1
7
3 -1
3 1
2 1
3 3
0 0
3 -3
2 -1
Вихідні дані #1
1 2 3
3 4 5
5 6 7
7 1 3
3 5 7
Автор Александр Миланин
Джерело Летняя школа Севастополь 2013, Волна 2, День 3