Çoxbucaqlının triqanqlyasiyası#5958
Çoxbucaqlı N zirvədən ibarətdir. Bu çoxbucaqlı öz-özünə kəsişmir və toxunmur. Sizin vəzifəniz bu çoxbucaqlını dəqiq N-2 üçbucağa bölməkdir. Bölmənin aşağıdakı şərtlərə cavab verməsi tələb olunur:
Hər üçbucağın zirvələri ilkin çoxbucaqlının zirvələrindən seçilməlidir;
Hər üçbucaq degenerasiya olunmamalıdır (yəni, sahəsi sıfır olmamalıdır);
Hər üçbucaq tamamilə ilkin çoxbucaqlının daxilində yerləşməlidir;
Hər hansı iki üçbucağın daxili sahələri bir-birinə toxunmamalıdır.
Birinci sətrdə çoxbucaqlının zirvələrinin sayı olan N (3 ≤ N ≤ 5000) ədədi verilir. Sonrakı N sətirdə, hər birində iki tam ədəd: x_i, y_i (-10000 ≤ x_i, y_{i} ≤ 10000) — çoxbucaqlının zirvələrinin saat əqrəbi istiqamətinin əksinə olan koordinatları verilir. Bütün nöqtələrin müxtəlif olduğu təmin edilir. Hər hansı iki tərəfin yalnız bir ortaq nöqtəsi olduğu təmin edilir, əgər tərəflər qonşudursa, əks halda heç biri yoxdur.
N-2 sətir, hər biri üç fərqli tam ədəd ehtiva edir: a_i, b_i və c_i (1 ≤ a_i, b_i, c_{i} ≤ N) — ilkin çoxbucaqlının i-ci üçbucağını təşkil edən zirvələrin nömrələri. İlkin çoxbucaqlının zirvələri giriş məlumatlarında görünmə sırasına görə 1-dən başlayaraq nömrələnir.
Əgər bir neçə poliqonun triqanqlyasiya həlli varsa, istənilənini çıxarmaq olar. Üçbucaqlar istənilən sırada çıxarıla bilər. Üçbucaqların zirvə nömrələri istənilən sırada çıxarıla bilər.
Nümunə 1