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

1600. Аэропорт

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В аэропорту Кольцово установили новую систему предотвращения столкновений самолетов. В определенном радиусе действия она следит за всеми летающими объектами: самолетами, вертолетами, парашютистами. Система предполагает, что все они движутся прямолинейно с постоянной скоростью, и в каждый момент времени просчитывает их движение на основе этой модели. Если какая-то пара объектов через некоторое время оказывается на критическом расстоянии d, то система бьет тревогу. Даны координаты и скорости объектов. Определите ту пару, которая раньше всех сблизится до расстояния d.

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

В первой строке заданы числа n — количество объектов в зоне ответственности системы (не более 500), и d — критическое расстояние (от 0.1 до 10000). В каждой из следующих n строк приведены текущие координаты (x, y и z) и составляющие скорости очередного объекта (vx, vy и vz). Значения координат не превосходят по модулю 10000, скорость не превосходит 100 по величине. Изначально все объекты находятся на безопасном расстоянии.

Результат

Если система будет бить тревогу, то в первой строке выведите «ALARM!». Во второй строке выведите время t (с точностью до трех знаков после десятичной точки), через которое случится первое опасное сближение, а также a и b — номера объектов, с которыми это произойдет. Если в момент времени t опасно сблизились сразу несколько пар объектов, то выведите любую из этих пар. Объекты пронумерованы от 1 до n в том порядке, в котором они перечислены во входных данных. Если все объекты благополучно разлетятся, то выведите «OK».

Пример

исходные данныерезультат
2 1.0
1.0 1.0 -1.0 0.0 0.0 10.0
0.0 0.0 4.0 2.0 0.0 0.0
ALARM!
0.500 1 2
Автор задачи: Владимир Яковлев
Источник задачи: Девятое открытое личное первенство УрГУ (1 марта 2008)