55. Злые свинки

Не решаласьЛёгкая

Вы никогда не задумывались, почему в Angry Birds у птиц нет крыльев? Тем же вопросом задались разработчики новой игры. В их версии смысл игры прямо противоположен Angry Birds: зеленая свинка стреляет по злым птицам из лазерного ружья (завязка явно не хуже исходной игры).

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

Формат ввода

Первая строка входного файла содержит единственное целое число N (1  $\le$  N  $\le$  1000) — количество птиц.

Следующие N строк содержат по два натуральных числа каждая $x_i$, $y_i$ — координаты i-ой птицы (0  $\lt$  x, y  $\le$$10^9$). Свинка находится в точке с координатами (0, 0).

Формат вывода

Единственная строка выходного файла должна содержать одно целое число — минимальное количество выстрелов, необходимое для того, чтобы сбить всех птиц.

Ограничения

Ограничение времени

1 с

Ограничение памяти

64 МБ

Пример 1

Ввод
6
1 1
2 2
3 3
2 1
3 2
3 1
Вывод
3

Пример 2

Ввод
6
1 1
2 2
3 3
2 1
3 2
3 4
Вывод
3

Теги

Нужно войти, чтобы отправить решение.Войти