Ланцюг-Обмежений Шлях#3770

Ланцюг-Обмежений Шлях

8 секунд

64 мегабайти

Дуже складна

На площині розташовано ланцюг із кількох кіл. Перше (і останнє) коло ланцюга перетинається лише з наступним (попереднім) колом, а кожне проміжне коло — лише з двома сусідніми.

Ваше завдання — знайти найкоротший шлях, що задовольняє наступним умовам:

Шлях з'єднує центри першого та останнього кіл.
Шлях залишається в межах ланцюга, тобто всі точки шляху перебувають всередині або на хоча б одному з кіл.

На рисунку 1 показано приклад такого ланцюга та відповідний найкоротший шлях.

Рисунок 1: Приклад ланцюга та відповідний найкоротший шлях

Вхідні дані

Вхід складається з кількох наборів. Кожен набір описує кола ланцюга у такому форматі:

У першому рядку задано ціле число $n$ ( $3 \leq n \leq 100$ 3 \leq n \leq 100) — кількість кіл. Кожен з наступних $n$ рядків містить три цілих числа $x_{i}$ x_i, $y_{i}$ y_i та $r_{i}$ r_i, розділених пробілами, що описують координати центра і радіус $i$ -го кола $C_{i}$ C_i. Гарантується, що $0 \leq x_{i} \leq 1000$ 0 \leq x_i \leq 1000, $0 \leq y_{i} \leq 1000$ 0 \leq y_i \leq 1000, $1 \leq r_{i} \leq 25$ 1 \leq r_i \leq 25.

Гарантується, що $C_{i}$ C_i і $C_{i + 1}$ C_{i+1} ( $1 \leq i \leq n - 1$ 1 \leq i \leq n-1) перетинаються у двох різних точках. Для $j \geq i + 2$ j \geq i+2 кола $C_{i}$ C_i і $C_{j}$ C_j не перетинаються і жодне не містить інше. Крім того, жодне коло не містить центр іншого.

Кінець введення позначається рядком, що містить один нуль.

Рисунок 1 відповідає першому набору з прикладу нижче. На рисунку 2 зображено найкоротші шляхи для наступних наборів.

Рисунок 2: Більше прикладів ланцюгів та найкоротших шляхів

Вихідні дані

Для кожного набору виведіть єдиний рядок із довжиною найкоротшого шляху, обмеженого ланцюгом, між центрами першого та останнього кіл. Відповідь повинна бути з похибкою не більше $0.001$ . У виводі не повинно бути зайвих символів.

Приклади

Приклад 1