Тріангуляція багатокутника#5958

Тріангуляція багатокутника

2 секунди

256 мегабайтів

Легка

Дано багатокутник з $N$ вершинами. Він не має самоперетинів і самоторкань. Ваше завдання — виконати тріангуляцію цього багатокутника, тобто розбити його на $N - 2$ N-2 трикутники, дотримуючись таких умов:

вершини кожного трикутника повинні бути серед вершин початкового багатокутника;
кожен трикутник має бути невиродженим;
кожен трикутник повністю міститься всередині початкового багатокутника;
внутрішні області будь-яких двох трикутників не повинні перетинатися.

Вхідні дані

Перший рядок містить число $N$ ( $3 \leq N \leq 5000$ 3 \leq N \leq 5000) — кількість вершин багатокутника. Далі йдуть $N$ рядків, кожен з яких містить два цілі числа: $x_{i}, y_{i}$ x_i,\ y_i ( $- 10000 \leq x_{i}, y_{i} \leq 10000$ -10000 \leq x_i,\ y_i \leq 10000) — координати вершин багатокутника в порядку обходу проти годинникової стрілки. Гарантується, що всі точки різні. Гарантується, що будь-яка пара сторін має рівно одну спільну точку, якщо сторони сусідні, і жодної в іншому випадку.

Вихідні дані

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

Якщо існує кілька варіантів тріангуляції, можна вивести будь-який з них. Трикутники можна виводити в будь-якому порядку. Номери вершин трикутників також можна виводити в будь-якому порядку.

Приклади

Приклад 1