e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

Выпуклая оболочка 3D - 3

Выпуклая оболочка 3D - 3

Даны n точек в пространстве. Никакие 4 точки не лежат в одной плоскости. Найдите выпуклую оболочку этих точек.

Входные данные

Первая строка содержит число n (4n100). Далее, в n строках даны по три числа — координаты точек. Все координаты целые, не превосходят по модулю 500.

Выходные данные

В первую строку выведите количество граней m. Далее в последующие m строк выведите описание граней: количество вершин и номера точек в исходном множестве. Точки нумеруются в том порядке, в котором они даны во входном файле. Точки в пределах грани должны быть отсортированы в порядке против часовой стрелки относительно внешней нормали к грани.

Лимит времени 2 секунды
Лимит использования памяти 256 MiB
Входные данные #1
4
0 0 0
1 0 0
0 1 0
0 0 1
Выходные данные #1
4
3 0 1 3
3 0 2 1
3 0 3 2
3 1 2 3
Автор Станислав Пак
Источник Зимняя Школа, Харьков 2011, День 1