Postanowiłeś na Saharze założyć radio. Od Ruskich możesz kupić stary nadajnik radiowy, pamiętający jeszcze czasy Lenina. Ten nadajnik ma jedną wadę - potrafi nadawać tylko w określonym kierunku, będącym kątem o rozwartości 90 stopni. Na Saharze jest n oaz o znanych Ci współrzędnych. Musisz założyć radiostację w jednej z oaz i tak ustawić nadajnik, by nadawał on do wszystkich oaz na Saharze, czyli, by wszystkie oazy mieściły się jednym kącie o rozwartości 90 stopni i o wierzchołku w wybranej oazie. To ty wybierasz, w jakim kierunku jest skierowany nadajnik.
W pierwszej linii wejścia jest liczba 3 <= n <= 20000, oznaczająca liczbę oaz na Saharze. Kolejne n linii zawiera po dwie liczby -1 000 000 000 <= x,y <= 1 000 000 000, oznaczające współrzędne kolejnej oazy. Oazy są parami różne. Twój program ma wypisać w pierwszej linii wyjścia liczbę k, oznaczającą liczbę oaz , w których można założyć radiostację, a następnie wypisać k linii, w każdej linii ma być numer oazy, w której można założyć radiostację. Numery mają być wypisane rosnąco; pierwsza oaza z pliku wejściowego to oaza o numerze 1, ostania - o numerze n.
Dla pliku wejściowego:
6 0 0 7 0 5 5 0 3 1 1 1 2
prawidłową odpowiedzią jest:
3 1 2 3
można założyć radiostacje w pierwszych trzech oazach.
[Zgłoś rozwiązanie] [Moje zgłoszenia]