I Mistrzostwa Wielkopolski
w Programowaniu Zespołowym

G - Skąpiec

Opis

Na dalekim wschodzie istnieje kraina, na której ludziom żyje się bardzo ciężko. Charakteryzuje się ona tym, że jest cała pokryta bardzo twardym podłożem. Utrudnia to bardzo życie mieszkańcom. np. w ziemi nie można kopać przez to dziur. Pewnego razu na tę trudną krainę przeprowadził się Bardzo Chciwy Skąpiec. Tak chciwy, że kraina ta jeszcze takiego nie widziała. Pierwsze, co postanowił zrobić po przyjeździe, to ogrodzić ziemię, którą tam zakupił, żeby nikt niepowołany po niej nie chodził. Niestety okazało się, że wbicie w ziemię palików, na których można by ustawić płot jest prawie niemożliwe. Żeby to zrobić trzeba wynająć ciężki sprzęt, a tego Skąpiec nie chce, bo to kosztuje. Na szczęście dla niego, zauważył, że cała ziemia pokryta jest małymi otworami, jakimiś pozostałościami polodowcowymi. Otwory te są w sam raz, żeby wsadzić w nie palik do postawienia płotu. Skąpiec za małe pieniądze wynajął sobie ludzi, żeby ogrodzili mu jak najwięcej jego terenu. Ponieważ chce zużyć jak najmniej siatki, postanowił sobie, że ustawi płot w kształcie koła. Wiadomo, że żeby płot w kształcie koła był stabilny musi się opierać przynajmniej na 3 palikach. Ludziom, których Skąpiec najął do pracy kazał wyznaczyć największy obszar, który można otoczyć przy pomocy okrągłej siatki zaczepionej w 3 punktach. Najemnicy zrobili tak, jak Skąpiec im nakazał. Ale wtedy stało się! Skąpiec wpadł w jedną z takich dziur i skręcił sobie nogę. Stwierdził więc, że nie może być tak, żeby na jego działce wewnątrz płotu były jakieś dziury (ale mogą one być w miejscu, przez które przechodzi płot). Kazał więc rozebrać postawioną siatkę i postawić nową. Kazał też tak ją postawić, żeby ogrodzić jak najwięcej terenu, tak żeby w środku nie było żadnej dziury. A najemnicy, jak to pracownicy. Okazało się, że jeden z palików wbili tak głęboko, że za nic nie chciał wyjść. Postanowili więc, że nie będą go wyciągać, tylko dwa pozostałe rozstawią tak, żeby ogrodzić teren bez dziur w środku. Co więcej postanowili wykorzystać fakt, że Skąpiec leży w szpitalu i planuję postawić jakikolwiek okrągły płot oparty na 3 palach, który nie ma w środku dziur.

Zadanie

Wiedząc jak są rozłożone dziury na terenie Skąpca i w której z nich jest palik, którego nie można było wyciągnąć, pomóż jego najemnikom wybrać pozostałe dwie dziury do włożenia palików tak, aby można było ogrodzić teren bez dziur. Nie interesuje nas to, czy starczy im siatki na budowę nowego płotu (promień może być dowolny). Nie interesuje nas też, czy budując płot ogradzający teren bez dziur nie zagarniemy kawałka działki sąsiada. Zakładamy, że nie ma innych dziur poza tymi na działce Skąpca. Dla uproszenia należy przyjąć, że płot ma szerokość 0, a dziury są punktami.

Specyfikacja wejścia

W pierwszej linii wejścia znajduje się jedna dodatnia liczba całkowita, oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. Każdy zestaw ma następującą postać. W pierwszej linii znajduje się jedna liczba całkowita N (3 ≤ N ≤ 10.000), która oznacza liczbę dziur na terenie należącym do Skąpca (dziury ponumerowane są od 1 do N). W liniach od 2 do N+1 zestawu znajdują się dwie liczby całkowite z przedziału od -10.000 do 10.000. Liczby w i+1 linii zestawu określają współrzędne i-tej dziury na wprowadzonym dla naszych potrzeb układzie współrzędnych na terenie Skąpca. Pierwsze z wymienionych współrzędnych są współrzędnymi punktu, w którym utknął palik. Żadne trzy punkty nie są współliniowe.

Specyfikacja wyjścia

Dla każdego zestawu danych pojawiającego się na wejściu należy wypisać trzy liczby oddzielone spacjami oznaczające numery dziur, w których będą wbite paliki. W przypadku możliwej większej liczby rozwiązań, należy wypisać dowolne z nich.

Przykład

Wejście

2
3
2 2
3 3
1 2
6
1 1
2 1
3 2
4 2
5 0
5 -12

Wyjście

2 3 1
1 2 3