Операция: Торговец Буриней
Маленькие девочки и мальчики на судах тоже заслуживают жуткого Рождества! Но доставка подарков движущимся целям может стать настоящей головной болью. Проблема в том, что вам нужно направить свои сани-гробы туда, где судно будет, а не туда, где оно находится сейчас. Король Тыкв попросил вас написать программу, которая поможет ему в этом, и, учитывая набор судов, спланировать маршрут, который займет минимальное количество времени для выполнения.
Вам будут даны начальные координаты саней и каждого судна, на котором находятся дети. Каждое судно постоянно движется по курсу и скорости, указанным вектором скорости (v_x, v_y), что означает, что через 1 час оно пройдет v_x км в направлении x и v_y км в направлении y (v_x и v_y могут быть отрицательными). Длина вектора — это скорость. Сани Джека способны двигаться с постоянной скоростью в любом направлении (предполагается, что ускорение и замедление происходят мгновенно). Джек должен приземлиться на каждом судне хотя бы один раз, и на каждой остановке требуется 5 минут для разгрузки подарков. Сани могут перевозить достаточно подарков для всех детей, не возвращаясь в Город Тыкв. Все координаты имеют единицы измерения в км, а все скорости и скорости — в км/ч.
Найдите минимальное время, за которое Джек сможет доставить подарки на каждое судно и вернуться в начальную точку.
Входные данные
Входные данные состоят из нескольких случаев. Каждый случай начинается с строки, содержащей целое число 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. Время должно быть округлено до следующей секунды.