Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TRNGLFLD - Trójkątne Pola

Pewien emerytowany matematyk osiadł na wsi — rolnictwo stało się jego hobby. Kupił więc sobie spory obszar ziemi i rozpoczął uprawę. Jak łatwo się domyślić, matematyk zachowuje się bardziej matematycznie niż przeciętny rolnik i w związku z tym jego pola z uprawami nie są w kształcie tradycyjnego prostokąta, lecz w kształcie trójkąta ostrokątnego. Co więcej, trójkąty z różnymi uprawami nie są obok siebie, jak to zazwyczaj bywa, lecz zawierają się w sobie. Dla każdej pary trójkątów albo jeden zawiera się w drugim, albo odwrotnie.

Matematyk ogrodził każde ze swoich trójkątnych pól uprawnych, żeby w przyszłości móc odróżnić gdzie co uprawia. Początkowo po prostu wbił metalowe pręty w miejscach wierzchołków trójkątów, na których rozpostarł taśmy udające ogrodzenia, z późniejszym zamiarem postawienia bardziej trwałych płotów. Niestety, nim zdążył zrealizować swój zamiar, wichura zerwała wszystkie taśmy. Teraz musi odtworzyć na nowo wszystkie ogrodzenia. Na jego nieszczęście nie można łatwo wizualnie rozpoznać granic między polami. Matematyk musi zatem wspomóc się położeniem prętów, które pozostały nie naruszone.

Zadanie

Dane są punkty będące wierzchołkami trójkątów, zgodnych z opisanymi powyżej fanaberiami matematyka (wierzchołki podane są w dowolnej kolejności). Odtwórz te trójkąty.

Specyfikacja wejścia

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę zestawów danych. Opis każdego z zestawu danych zaczyna się od linii z jedną liczbą całkowitą N (3 ≤ N ≤ 45000), podzielną przez 3, oznaczającą liczbę punktów. W kolejnych N liniach zestawu zapisane są ich współrzędne w postaci dwóch liczb całkowitych x i y (–1000000000 ≤ x, y ≤ 1000000000). Punkty w obrębie jednego zestawu danych są parami różne. Należy założyć, że z punktów podanych na wejściu będzie dało się skonstruować trójkąty zgodnie z warunkami opisanymi w treści zadania.

Specyfikacja wyjścia

Dla każdego zestawu danych należy wypisać N/3 linii z opisami trójkątów. Każda z nich powinna zawierać trzy liczby, będące numerami punktów połączonych w trójkąt (punkty numerowane są począwszy od 1). Trójkąty należy podawać w kolejności od najbardziej zewnętrznego do najbardziej wewnętznego. W obrębie trójkąta punkty należy podawać w kolejności rosnących numerów. W przypadku gdy istnieje kilka rozwiązań, wystarczy podać dowolne z nich. Zestawy danych powinny być oddzielone od siebie pustą linią (pusta linia na końcu pliku jest zbędna, choć będzie akceptowana).

Przykład

Wejście

2
3
0 0
1 2
2 1
6
-2 0
2 0
1 1
-1 1
0 3
0 4

Przykładowe wyjście

1 2 3
      
1 2 6
3 4 5

Dodane przez:Rafal Nowak
Data dodania:2005-02-10
Limit czasu wykonania programu:5s
Limit długości kodu źródłowego5000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:II Mistrzostwa Wielkopolski w Programowaniu Zespołowym
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.