e-olymp
Məsələlər

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

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

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).

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
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
Çıxış verilənləri
237
18