Місія постачання#2760

Місія постачання

3 секунди

64 мегабайти

Складна

Ви керуєте гелікоптером, щоб доставити припаси до кількох підводних човнів, які наразі рухаються океаном. Дані координати гелікоптерної бази та кожного підводного човна, а також швидкості кожного човна і швидкість гелікоптера. Кожен підводний човен рухається постійно з напрямком і швидкістю, заданими вектором швидкості $(v x, v y)$ (vx, vy), тобто через $1$ годину він подолає $v x$ км по осі $x$ і $v y$ км по осі $y$ ( $v x$ та $v y$ можуть бути від'ємними). Довжина цього вектора визначає швидкість. Гелікоптер може летіти із сталою швидкістю в будь-якому напрямку (вважайте, що розгін і гальмування відбуваються миттєво).

Гелікоптер повинен приземлитися на кожному підводному човні щонайменше один раз, і на кожній зупинці потрібно $1$ годину, щоб розвантажити припаси і дозаправитися. Кожен підводний човен піднімається на поверхню у відповідний момент приземлення гелікоптера і занурюється одразу після того, як гелікоптер залишає його. Швидкість підводного човна не залежить від глибини. Гелікоптер може взяти стільки припасів, щоб доставити їх усім човнам без повернення на базу. Всі координати задані в кілометрах, всі швидкості — в кілометрах на годину. Вважайте, що гелікоптер летить швидше будь-якого підводного човна. Зауважте, що траєкторії підводних човнів можуть перетинатися між собою чи з базою гелікоптера, але оскільки вони можуть регулювати глибину, зіткнень не буде.

Знайдіть найменший час, необхідний гелікоптеру, щоб доставити припаси до кожного підводного човна і повернутися на базу.

Вхідні дані

Вхід складається з кількох тестових випадків. Кожен випадок починається рядком з одного цілого числа $N$ ( $1 \leq N \leq 8$ 1 \leq N \leq 8) — кількості підводних човнів. Далі йде $N$ рядків, кожен з яких містить $4$ цілих числа: початкові координати $(x, y)$ $i$ -го підводного човна та його вектор швидкості. Останній рядок кожного випадку містить $3$ цілих числа — координати $(x, y)$ гелікоптерної бази і швидкість гелікоптера. Кінець вводу позначає випадок, що починається з $N = 0$ N = 0; цей випадок не слід обробляти. Всі цілі числа вхідних даних за модулем не більші за $1000$ .

Вихідні дані

Для кожного випадку виведіть його номер, двокрапку, а далі мінімальний час, необхідний для виконання завдання, у такому форматі:

Case a: b hour(s) c minute(s) d second(s)

де $a$ , $b$ , $c$ , $d$ — відповідні невід'ємні цілі числа, причому $c$ і $d$ не повинні перевищувати $59$ . Час слід округлити вгору до наступної секунди.

Приклади

Приклад 1