Ogródek
Limit pamięci: 64 MB
Żona Bajtazara, Bajtolina, uwielbia kwiaty i postanowiła
założyć ogródek nieopodal domu małżeństwa. Ponieważ Bajtolina jest perfekcjonistką,
chciałaby, aby jej ogródek był kwadratowy, a jego boki były równoległe do najbliższego
południka i równoleżnika. Ponadto, Bajtolina zażyczyła sobie, aby w każdym rogu
ogródka znajdowała się jedna z rosnących w pobliżu jabłoni.
Informacja o planach żony, a także o tym, że ogródek musi być wybudowany natychmiast,
zaskoczyła Bajtazara dokładnie w momencie, gdy zaczynał się finał piłkarskich mistrzostw
świata. Bajtazar dobrze wie, że jego żona to osoba, której się nie odmawia, dlatego
zachował zimną krew i zapytał ją wymijająco czy wie, w którym miejscu chciałaby
wybudować ogródek. Bajtolina, będąc perfekcjonistką, na pewno sprawdzi wszystkie
możliwe położenia ogrodu, zanim się na którąś zdecyduje. Bajtazar chciałby szybko się
dowiedzieć, ile czasu jej to zajmie, przyjmując, że każde możliwe położenie ogrodu
jego żona jest w stanie ocenić w czasie jednej sekundy.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się jedna liczba całkowita
,
, oznaczająca liczbę jabłoni rosnących nieopodal domu małżonków.
Dla uproszczenia położenie drzew określamy w kartezjańskim układzie współrzędnych,
w którym najbliższym południkiem jest oś
, a najbliższym równoleżnikiem - oś
.
W każdym następnych
wierszów znajdują się dwie oddzielone pojedynczym odstępem
liczby całkowite
i
,
, oznaczające
współrzędne
-tego drzewa. Żadna para współrzędnych nie powtórzy się na wejściu.
Wyjście
Na standardowe wyjście należy wypisać jedną liczbę całkowitą równą liczbie sekund,
które Bajtolina potrzebuje, aby sprawdzić wszystkie możliwości położenia
kwadratowego ogrodu, który w każdym narożniku ma jedną z jabłoni.
Przykład
Dla danych wejściowych:
6
0 0
0 1
1 0
1 1
3 0
3 1
poprawną odpowiedzią jest:
1
Autor zadania: Neal Wu (tłumaczenie: Adam Karczmarz).