Миссия по снабжению
Вы управляете вертолетом, который должен доставить припасы на несколько подводных лодок, движущихся по океану. Вам предоставлены координаты базы вертолета и каждой подводной лодки. Каждая подводная лодка движется с постоянной скоростью, заданной вектором (vx, vy), что означает, что за 1 час она перемещается на vx км по оси x и на vy км по оси y (vx и vy могут быть отрицательными). Длина этого вектора определяет скорость. Вертолет может лететь с постоянной скоростью в любом направлении (предполагается, что ускорение и торможение происходят мгновенно). Вертолет должен приземлиться на каждую подводную лодку хотя бы один раз, и на каждой остановке требуется 1 час для разгрузки припасов и дозаправки. Подводная лодка всплывает на поверхность в момент посадки вертолета и погружается сразу после его отлета. Скорость подводной лодки не изменяется при изменении глубины. Вертолет может перевозить достаточно припасов для всех подводных лодок без необходимости возвращаться на базу. Все координаты измеряются в км, а скорости — в км/ч.
Определите минимальное время, за которое вертолет сможет доставить припасы на каждую подводную лодку и вернуться на базу.
Входные данные
Входные данные состоят из нескольких случаев. Каждый случай начинается с строки, содержащей целое число N (1 ≤ N ≤ 8), обозначающее количество подводных лодок. Следующие N строк содержат 4 целых числа, разделенных пробелом: начальные координаты (x, y) i-й подводной лодки и ее вектор скорости. Последняя строка каждого случая содержит 3 целых числа, указывающих координаты (x, y) базы вертолета и скорость вертолета. Ввод заканчивается случаем, который начинается с N = 0; этот случай не обрабатывается. Все входные целые числа имеют абсолютное значение не более 1000. Предполагается, что вертолет движется быстрее любой подводной лодки. Обратите внимание, что пути подводных лодок могут пересекаться друг с другом или с базой вертолета, но благодаря возможности регулировать глубину, столкновений не произойдет.
Выходные данные
Для каждого случая выведите его номер, двоеточие, затем минимальное время, необходимое для выполнения миссии, в формате:
Case a: b hour(s) c minute(s) d second(s)
где a, b, c, d — соответствующие неотрицательные целые числа, и c и d не превышают 59. Время должно быть округлено до ближайшей секунды.