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

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

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

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

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

Первая строка содержит число m — количество тестов. В последующих строках описаны сами тесты. Каждый тест начинается со строки, содержащей n (1n1000) — число точек. Далее, в n строках даны по три числа — координаты точек. Все координаты целые, не превосходят по модулю 500. Общее количество точек не превосходит 2100.

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri
2
4
0 0 0
1 0 0
0 1 0
0 0 1
5
0 0 0
10 0 0
0 10 0
10 10 10
5 5 10
Çıxış verilənləri
4
3 0 1 3
3 0 2 1
3 0 3 2
3 1 2 3
6
3 0 1 4
3 0 2 1
3 0 4 2
3 1 2 3
3 1 3 4
3 2 4 3
Müəllif Станислав Пак
Mənbə Зимняя школа, Харьков 2011, День 1