Опукла оболонка 3D - 1#1833

Опукла оболонка 3D - 1

1 секунда
256 мегабайтів
Середня

точок задано у просторі. Жодні чотири точки не лежать в одній площині. Знайдіть опуклу оболонку цих точок.

Вхідні дані

У першому рядку задано — кількість тестових випадків. Далі слідують описи тестів. Кожен тест починається з рядка, що містить (1 \leq n \leq 1000) — кількість точок. Далі йдуть рядків, у кожному з яких задано по три цілі числа — координати точок. Усі координати — цілі числа із модулем не більше . Загальна кількість точок у всіх тестах не перевищує .

Вихідні дані

Для кожного тестового випадку виведіть наступне. У першому рядку виведіть кількість граней . У наступних рядках наведіть опис кожної грані: кількість вершин та індекси точок із заданої множини. Точки нумеруються у порядку, в якому вони з'являються у вхідному файлі. У межах кожної грані точки мають бути перераховані у протилежному до годинникової стрілки порядку відносно зовнішньої нормалі цієї грані.

Приклади

Приклад 1

Loading
Loading