Місія постачання
Вам потрібно керувати вертольотом, щоб доставити припаси до кількох підводних човнів, які рухаються океаном. Ви отримаєте координати бази вертольота та кожного підводного човна. Кожен підводний човен постійно рухається з певною швидкістю, заданою вектором (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. Ви можете припустити, що вертоліт рухається з більшою швидкістю, ніж кожен підводний човен. Зверніть увагу, що шляхи підводних човнів можуть перетинатися між собою або навіть з базою вертольота, але оскільки вони можуть регулювати свою глибину, зіткнень не буде.
Вихідні дані
Для кожного випадку виведіть номер випадку, двокрапку, а потім мінімальний час, необхідний для завершення місії у форматі:
Випадок a: b годин(и) c хвилин(и) d секунд(и)
де a, b, c, d є відповідними невід'ємними цілими числами, а c та d не перевищують 59. Час слід округлити вгору до наступної секунди.