Закріплена повітряна куля#6106

Закріплена повітряна куля

8 секунд

64 мегабайти

Дуже складна

Повітряна куля, що лежить на землі, прикріплена до одного або кількох якорів за допомогою мотузок. Кожна мотузка достатньо довга, щоб з'єднати повітряну кулю з якорем. Жодні дві мотузки не перетинаються. Рисунок 1 ілюструє цю ситуацію.

Рисунок 1: Повітряна куля та мотузки на землі

Повітряна куля починає підніматися, і ваше завдання — визначити, наскільки високо вона може піднятися, залишаючись прикріпленою мотузками. Позиції якорів залишаються незмінними. Довжини мотузок та координати якорів відомі. Ви можете вважати, що мотузки не мають ваги і можуть бути натягнуті в будь-якому напрямку. Рисунок 2 показує максимальну висоту повітряної кулі для ситуації з Рисунку 1.

Рисунок 2: Найвища позиція повітряної кулі

Вхідні дані

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

$n$

$x_{1} y_{1} l_{1}$ x_1\ y_1\ l_1

$\dots$

$x_{n} y_{n} l_{n}$ x_n\ y_n\ l_n

Перша строка кожного набору містить ціле число $n$ ( $1 \leq n \leq 10$ 1 \leq n \leq 10), що вказує на кількість мотузок. Кожна з наступних $n$ строк містить три цілі числа: $x_{i}$ x_i, $y_{i}$ y_i, та $l_{i}$ l_i, розділені пробілом. $P_{i} = (x_{i}, y_{i})$ P_i = (x_i,\ y_i) визначає позицію якоря для $i$ -тої мотузки, а $l_{i}$ l_i — довжину цієї мотузки. Ви можете вважати, що $- 100 \leq x_{i} \leq 100$ -100 \leq x_i \leq 100, $- 100 \leq y_{i} \leq 100$ -100 \leq y_i \leq 100, та $1 \leq l_{i} \leq 300$ 1 \leq l_i \leq 300. Повітряна куля спочатку знаходиться в точці $(0, 0)$ на землі. Розміри повітряної кулі та якорів можна ігнорувати.

Ви можете вважати, що $P_{i}$ P_i та $P_{j}$ P_j — це різні позиції, якщо $i \neq = j$ i \neq j. Також можна припустити, що відстань між $P_{i}$ P_i та $(0, 0)$ не перевищує $l_{i} - 1$ l_i - 1. Це означає, що повітряна куля може піднятися щонайменше на $1$ одиницю висоти.

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

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

Вихідні дані

Для кожного набору даних виведіть один рядок з максимальною висотою, на яку може піднятися повітряна куля. Похибка значення не повинна перевищувати $0.00001$ . У виході не повинно бути жодних зайвих символів.

Приклади

Приклад 1