Космический мусор
(Время: 5 сек. Память: 32 Мб Сложность: 38%)
Вокруг мирной космической станции накопилось много мусора, который летает в космосе. Он может быть как просто не приятен – загораживая обзор и исходящие сигналы, так и просто опасен – если станция начнёт движение, то может произойти столкновение.
Станция имеет на борту смертоносный лазерный луч, имеющий достаточную дальность для уничтожения любого из зафиксированных объектов. При этом луч достаточно мощный и поражает все объекты, находящиеся у него на пути.
Каждый объект зафиксирован и внесён в реестр в виде координат (x, y, z). Считается, что станция находится в начале координат (0, 0, 0). Размером объектов и станции нужно пренебречь, лазерный луч выходит из начала координат.
Подготовка луча – дело долговременное, поэтому вам нужно вычислить минимальное количество выстрелов, необходимое для уничтожения всех объектов.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N – количество объектов в космосе (1 ≤ N ≤ 200 000). В каждой из следующих N строк содержатся координаты объектов в виде целых чисел x, y, z (|x|, |y|, |z| ≤ 109). Координаты объектов могут совпадать. Гарантируется, что не существует объектов в начале координат.
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – необходимое количество выстрелов.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 4
0 1 0
-1 0 0
1 1 0
1 0 1 | 4 |
2 | 3
1 1 1
2 2 2
1 1 1 | 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|