Выпуклая оболочка
Выпуклая оболочка
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 (4 ≤ n ≤ 25), указывающих количество точек в X. Далее следует n строк, каждая из которых содержит 3 целых числа соответственно x, y и z координату очередной точки. Все координаты находятся в пределах от −100 до 100. Окончание входных данных заканчивается строкой n = 0, которую обрабатывать не нужно.
Выходные данные
Для каждого случая входных данных вывести единственную строку со значением искомой минимальной площади. Ответ должен быть округлен до ближайшего целого (например, 2.499 округливается к 2, а 2.5 округливается к 3).
Подсказка
Во избежание недоразумений все тестовые данные подобраны так, чтобы исключить неоднозначности при округлении с точностью до 0.001 (т.е. можно предположить, что площадь никогда не будет типа 2.4997).
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
237 18