Голодный ферзь - 2

Голодный шахматный ферзь стоит на поле (0, 0) бесконечной шахматной доски. Также на доске расположено n пешек, пронумерованных от 1 до n, i-я пешка стоит на поле (x_i, y_i).

Ферзь планирует побить как можно больше пешек. При этом ферзь должен бить пешки по порядку: сначала первую, затем вторую, и т.д. Все ходы ферзя должны удовлетворять правилам шахмат: он должен ходить по горизонтали, вертикали или диагонали. Ферзь должен брать пешку каждым ходом. Не разрешается перепрыгивать через пешки. Взятая пешка снимается с доски. Пешки не перемещаются.

Выясните, какое максимальное количество пешек ферзь может побить.

Входные данные

Первая строка входного файла INPUT.TXT содержит число n – количество пешек (1 ≤ n ≤ 10⁵). Следующие n строк содержат по два целых числа (x_i, y_i) – координаты пешек, не превосходящие 10⁹ по абсолютной величине. На поле (0, 0) пешки нет, никакие две пешки не находятся на одном и том же поле.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число – количество пешек, которые ферзь может побить.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]