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