eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

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

Розглянемо, наприклад, X = {(0, 0, 0), (10, 0, 0), (0, 10, 0), (0, 0, 10)}. Опукла оболонка X у даному випадку є тетраедром з вершинами, визначеними в X. Відмітимо, що цей тетраедр містить і точку з координатами (1, 1, 1), так що додавання вказаної точки не змінить опуклу оболонку.

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

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

Вхідні дані

Вхідні дані містять декілька тестових випадків, кожен з яких починається з цілого числа n (4n25), яке вказує кілікість точок в X. Далі йде n рядків, кожен з яких містить 3 цілих числа відповідно x, y і z координату чергової точки. Всі координати знаходяться в межах від −100 до 100. Завершення вхідних даних позначається рядком n = 0, який опрацьовувати не потрібно.

Вихідні дані

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

Підказка

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

Приклад

Вхідні дані #1
5
0 0 0
10 0 0
0 10 0
0 0 10
1 1 1
9
0 0 0
2 0 0
2 2 0
0 2 0
1 1 2
1 1 -2
1 1 -1
1 1 0
1 1 1
0
Вихідні дані #1
237
18