Страница: 1 Отображать по:
#3594
Злые свинки или Anti Angry Birds
  
Темы: [Множества]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

Следующие N строк содержат по два натуральных числа каждая xi, yi — координаты i-ой птицы (0 < x, y ≤ 109). Свинка находится в точке с координатами (0, 0).

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

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

Примеры
Входные данные
6
1 1
2 2
3 3
2 1
3 2
3 1
Выходные данные
3
Входные данные
6
1 1
2 2
3 3
2 1
3 2
3 4
Выходные данные
3
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест