ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1477. Самолёты

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Вы, вероятно, бывали в аэропортах, в которых самолёты взлетают с интервалом в одну минуту или даже чаще. А вы не задумывались, сколько самолётов одновременно находится в воздухе? А в масштабах целого земного шара?
Будем считать, что Земля — идеальный шар с центром в точке (0, 0, 0) радиусом 6370 километров. Большинство пассажирских самолётов летает на высоте не более 15 километров. Если бы вам удалось посмотреть на земной шар со стороны, самолёты выглядели бы точками на его поверхности. Пусть в какой-то момент времени в воздухе находится N самолётов. Самолёт с номером i находится в точке пересечения земной сферы с лучом, исходящим из начала координат по направляющему вектору (Xi, Yi, Zi). Над каждой точкой земной поверхности находится не более одного самолёта. Ваша задача — посчитать, какое максимальное количество самолётов вы могли бы увидеть, находясь на очень большом расстоянии от Земли. С такого расстояния вы можете наблюдать некоторую открытую полусферу Земли.

Исходные данные

В первой строке находится целое число N (1 ≤ N ≤ 150). Далее в N строках задаются самолёты тройками целых чисел Xi, Yi, Zi. Все числа не превосходят по модулю 600. Хотя бы одно число в каждой тройке не равно 0.

Результат

Программа должна найти наибольшее количество самолётов, которое вы можете увидеть в описанный момент времени.

Пример

исходные данныерезультат
6
0 0 1
0 0 -1
0 1 0
0 -1 0
1 0 0
-1 0 0
3
Автор задачи: Дмитрий Иванков
Источник задачи: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006