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

Выпуклая оболочка

Выпуклая оболочка

\textbf{3}-х мерный объект называется выпуклым, если любой отрезок, соединяющий две его любые точки полностью принадлежит объекту. Для заданного множества точек \textbf{X} в \textbf{3}-х мерном пространстве, существует также \textit{выпуклая оболочка} \textbf{X} являющейся наименьшей выпуклой оболчкой, содержащей все заданные точки. Рассмотрим, например, \textbf{X} = \{(\textbf{0}, \textbf{0}, \textbf{0}), (\textbf{10}, \textbf{0}, \textbf{0}), (\textbf{0}, \textbf{10}, \textbf{0}), (\textbf{0}, \textbf{0}, \textbf{10})\}. Выпуклая оболочка \textbf{X} в данном случае является тетраэдром с вершинами, определенными в \textbf{X}. Заметим, что этот тетраэдр содержит и точку с координатами (\textbf{1}, \textbf{1}, \textbf{1}), так что добавление указанной точки не изменит выпуклую оболочку. Для заданного множества точек \textbf{X}, ваша задача состоит в нахождении наименьшей площади выпуклой оболочки \textbf{X}, округленной к ближайшему целому. \textbf{Примечание:} Любая выпуклая оболочка состоит из многоугольных граней. В этой задаче можно предположить, что на каждой грани будет не более \textbf{3}-х точек из \textbf{X}. \InputFile Входные данные содержат несколько тестовых случаев, каждый из которых начинается с целого числа \textbf{n} (\textbf{4} ≤ \textbf{n} ≤ \textbf{25}), указывающих количество точек в \textbf{X}. Далее следует \textbf{n} строк, каждая из которых содержит \textbf{3} целых числа соответственно \textbf{x}, \textbf{y} и \textbf{z} координату очередной точки. Все координаты находятся в пределах от \textbf{−100} до \textbf{100}. Окончание входных данных заканчивается строкой \textbf{n} = \textbf{0}, которую обрабатывать не нужно. \OutputFile Для каждого случая входных данных вывести единственную строку со значением искомой минимальной площади. Ответ должен быть округлен до ближайшего целого (например, \textbf{2.499} округливается к \textbf{2}, а \textbf{2.5} округливается к \textbf{3}). \textbf{Подсказка} Во избежание недоразумений все тестовые данные подобраны так, чтобы исключить неоднозначности при округлении с точностью до \textbf{0.001} (т.е. можно предположить, что площадь никогда не будет типа \textbf{2.4997}).
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #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