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

NEERC 2008, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Сомалийские пираты

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Из ленты новостей: «Сомалийские пираты захватили голландский корабль с русскими и филлипинцами на борту, плывущий под панамским флагом из Кении в Румынию и перевозящий немецкие нефтевышки.»
В этот раз в поле зрения пиратов попал голландский корабль «Молниеносный», перевозящий новейшую лазерную пушку. Конечно, они не могли оставить такой ценный груз без внимания. Пиратские корабли со всех сторон окружили голландское судно. Но русские матросы не растерялись и решили отстреливаться из лазерной пушки. Им нельзя подпустить к себе ни одного корабля ближе, чем на одну морскую милю, иначе пушку уже нельзя будет навести на цель, и команда попадет в плен.
Лазерная пушка может вращаться в любую сторону со скоростью не более w оборотов в минуту, при этом она стреляет мгновенно, даже не прекращая вращение. В результате выстрела корабль, находящийся на линии огня, сразу же тонет. Все пиратские корабли движутся строго в направлении голландского судна, каждый со своей постоянной скоростью vi узлов (1 узел равен 1 морской миле в час). Относительно «Молниеносного» i-й корабль движется по азимуту bi (азимут — это отклонение от направления на север по часовой стрелке в градусах). Азимуты всех кораблей различны. В начальный момент времени пушка направлена по азимуту a, а i-й пиратский корабль находится на расстоянии di морских миль от голландского судна. Можно считать, что «Молниеносный» стоит на одном месте.
Определите, в каком порядке нужно обстреливать пиратские корабли, чтобы потопить их все за минимальное время и не попасть в плен.

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

В первой строке заданы числа a, w и n (0 ≤ a < 360; 0.01 ≤ w ≤ 1; 1 ≤ n ≤ 500). В каждой из следующих n строк задано по три числа: bi, di и vi (0 ≤ bi < 360; 1 ≤ di ≤ 1000; 0.01 ≤ vi ≤ 100). Все числа даны не более чем с тремя знаками в дробной части.

Результат

Если матросам удастся потопить все пиратские корабли, то в первой строке выведите минимально необходимое для этого время в минутах с точностью до 10−3. В следующих n строках выведите порядок, в котором следует обстреливать корабли (они нумеруются от 1 до n в том порядке, в каком даны на вводе). Если отстреляться от пиратов невозможно, то выведите единственную строку «Impossible».

Примеры

исходные данныерезультат
0.0 0.05 2
144.0 22.0 100.0
216.0 22.0 100.0
12.000
2
1
0.0 0.05 2
144.0 20.0 100.0
216.0 20.0 100.0
Impossible
Автор задачи: Денис Мусин
Источник задачи: NEERC 2008, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1655. Сомалийские пираты