Məsələlər
Голодный ферзь 2
Голодный ферзь 2
Голодный шахматный ферзь стоит на поле (\textbf{0}, \textbf{0}) бесконечной шахматной доски. Также на доске расположено \textbf{n} пешек, пронумерованных от \textbf{1} до \textbf{n}, \textbf{i}-я пешка стоит на поле (\textbf{x_i}, \textbf{y_i}).
Ферзь планирует побить как можно больше пешек. При этом ферзь должен бить пешки по порядку: сначала первую, затем вторую и т.д. Все ходы ферзя должны удовлетворять правилам шахмат - он должен ходить по горизонтали, вертикали или диагонали. Ферзь должен брать пешку каждым ходом. Не разрешается перепрыгивать через пешки. Взятая пешка снимается с доски. Пешки не перемещаются.
Выясните, какое максимальное количество пешек ферзь может побить.
\InputFile
Первая строка входного файла содержит \textbf{n} - количество пешек (\textbf{1} ≤ \textbf{n} ≤ \textbf{100000}). Следующие \textbf{n} строк содержат координаты пешек (координаты не превышают по модулю \textbf{10^9}).
На поле (\textbf{0}, \textbf{0}) пешки нет, никакие две пешки не находятся на одном и том же поле.
\OutputFile
Выведите одно число - максимальное количество пешек, которое может побить ферзь.
Giriş verilənləri #1
4 0 2 1 1 1 -3 1 0
Çıxış verilənləri #1
2