Triangulyasiya
Verilmiş çoxbucaqlı N zirvədən ibarətdir. Bu çoxbucaqlı öz-özünə kəsişmir və toxunmur. Sizdən tələb olunan, bu çoxbucaqlını dəqiq N-2 üçbucağa bölməkdir, elə ki, aşağıdakı şərtlər ödənilsin:
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.
Giriş verilənləri
Birinci sətir çoxbucaqlının zirvələrinin sayı olan N (3 ≤ N ≤ 5000) ədədini ehtiva edir. 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 fərqli 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.
Çıxış verilənləri
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 triangulyasiya üçün bir neçə variant 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.