e-olymp
Задачі

Многогранник

Многогранник

Задано множину точок в тривимірному просторі. Ваша задача полягає в тому, щоб порахувати кількість граней з k вершинами опуклого многогранника мінімального об'єму, що містить всі задані точки.

Вхідні дані

У першому рядку міститься кількість тестів T (1T100). Перший рядок кожного тесту містить кількість точок у множині – N (4N30). Далі йде N рядків, кожен з яких містить 3 цілих числа: X, Y, Z (–1000X, Y, Z1000) – координати точок. Деякі точки можуть мати одні й ті самі координати! Гарантується, що довільний опуклий многогранник, що містить всі задані точки, буде мати додатній об'єм.

Вихідні дані

Для кожного з T тестів виведіть рядок вигляду "Case #A:", де A – номер тесту (починаючи з 1), а потім – ще M рядків, де M – кількість різних типів граней (під типом грані розуміється кількість її вершин). В кожному з наступних M рядків потрібно вивести два числа: k – кількість вершин в грані та qk – кількість k-вершинних граней в многограннику. Після k потрібно надрукувати двокрапку ":" і потім – пропуск. Результат потрібно виводити в порядку зростання k. Кількість вершин у грані визначається тільки з геометричних міркувань. Тобто, якщо задана точка лежить на стороні грані, вона не вважається вершиною, а якщо декілька таких точок лежать в одній вершині, їх треба вважати за одну вершину.

Ліміт часу 5 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані
2
6
0 0 0
2 0 0
0 2 0
2 2 0
3 1 0
1 1 1
5
0 0 0
1 1 0
0 2 0
2 1 0
1 1 1
Вихідні дані
Case #1:
3: 5
5: 1
Case #2:
3: 4