Опукла оболонка 3D - 2#1836

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

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

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

Вхідні дані

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

Вихідні дані

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

Приклади

Приклад 1

Loading
Loading