Опукла оболонка#1044

Опукла оболонка

1 секунда

64 мегабайти

Середня

3-вимірний об'єкт називається опуклим, якщо для будь-яких двох точок цього об'єкта відрізок, що їх з'єднує, повністю лежить всередині об'єкта. Для заданої множини точок $X$ у тривимірному просторі опукла оболонка множини $X$ — це найменше опукле тіло, яке містить усі точки з $X$ .

Наприклад, нехай $X = {(0, 0, 0), (10, 0, 0), (0, 10, 0), (0, 0, 10)}$ X = \{(0, 0, 0), (10, 0, 0), (0, 10, 0), (0, 0, 10)\}. Опукла оболонка $X$ — це тетраедр з вершинами у точках з $X$ . Зауважимо, що цей тетраедр також містить точку $(1, 1, 1)$ (1, 1, 1), тому додавання цієї точки до $X$ не змінить опуклу оболонку.

Дано множину точок $X$ . Ваше завдання — знайти площу поверхні опуклої оболонки множини $X$ , округлену до найближчого цілого числа.

Примітка: Кожна опукла оболонка складається з багатокутних граней. У цій задачі можна вважати, що на будь-якій грані опуклої оболонки буде щонайбільше $3$ точки з $X$ .

Вхідні дані

Вхід містить кілька тестових випадків. Кожен тестовий випадок починається з цілого числа $n$ ( $4 \leq n \leq 25$ 4 \le n \le 25) — кількість точок у $X$ . Далі йдуть $n$ рядків, кожен з яких містить $3$ цілих числа — координати $x$ , $y$ та $z$ точки. Усі координати знаходяться між $- 100$ та $100$ включно. Кінець вводу позначено рядком, де $n = 0$ n = 0; цей тестовий випадок не обробляється.

Вихідні дані

Для кожного тестового випадку виведіть у окремому рядку площу поверхні опуклої оболонки, округлену до найближчого цілого числа (наприклад, $2.499$ округлюється до $2$ , а $2.5$ — до $3$ ).

Підказка

Усі тестові випадки підібрано так, що при округленні з точністю до $0.001$ неоднозначності не виникає (тобто можна вважати, що площа ніколи не буде $2.4997$ ).

Приклади

Приклад 1