Триангуляция
Дан многоугольник из N вершин. Он не содержит самопересечений и самокасаний. Требуется произвести его триангуляцию, то есть, разбить его ровно на N-2 треугольника таким образом, что выполняется:
вершины каждого треугольника выбираются среди вершин исходного многоугольника;
каждый треугольник должен быть невырожденным;
каждый треугольник должен полностью содержаться в исходном многоугольнике;
внутренние области любых двух треугольников не пересекаются.
Входные данные
Первая строка содержит число N (3 ≤ N ≤ 5000) — количество вершин многоугольника. Далее N строк по два целых числа в каждой: x_i, y_i (-10000 ≤ x_i, y_{i }≤ 10000) — координаты вершин многоугольника в порядке обхода против часовой стрелки. Гарантируется, что все точки различные. Гарантируется, что любая пара сторон имеет ровно одну общую точку, если стороны соседние, и ни одной в противном случае.
Выходные данные
N-2 строки, каждая из которых содержит три различных целых числа: a_i, b_i и c_i (1 ≤ a_i, b_i, c_{i }≤ N) — номера вершин исходного многоугольника, которые формируют i-ый треугольник. Вершины исходного многоугольника нумеруются начиная с 1 в порядке появления во входных данных.
Если вариантов триангуляции несколько, можно вывести любой. Треугольники можно выводить в любом порядке. Номера вершин треугольников можно выводить в любом порядке.