eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Задано множину точок в тривимірному просторі. Ваша задача полягає в тому, щоб порахувати кількість граней з \textbf{k} вершинами опуклого многогранника мінімального об'єму, що містить всі задані точки. \InputFile У першому рядку міститься кількість тестів \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{100}). Перший рядок кожного тесту містить кількість точок у множині -- \textbf{N} (\textbf{4} ≤ \textbf{N} ≤ \textbf{30}). Далі йде \textbf{N} рядків, кожен з яких містить \textbf{3} цілих числа: \textbf{X}, \textbf{Y}, \textbf{Z} (\textbf{--1000} ≤ \textbf{X}, \textbf{Y}, \textbf{Z} ≤ \textbf{1000}) -- координати точок. Деякі точки можуть мати одні й ті самі координати! Гарантується, що довільний опуклий многогранник, що містить всі задані точки, буде мати додатній об'єм. \OutputFile Для кожного з \textbf{T} тестів виведіть рядок вигляду "\textbf{Case} #\textbf{A}:", де \textbf{A} -- номер тесту (починаючи з 1), а потім -- ще \textbf{M} рядків, де \textbf{M} -- кількість різних типів граней (під типом грані розуміється кількість її вершин). В кожному з наступних \textbf{M} рядків потрібно вивести два числа: \textbf{k} -- кількість вершин в грані та \textbf{q_k} -- кількість \textbf{k}-вершинних граней в многограннику. Після \textbf{k} потрібно надрукувати двокрапку ":" і потім -- пропуск. Результат потрібно виводити в порядку зростання \textbf{k}. Кількість вершин у грані визначається тільки з геометричних міркувань. Тобто, якщо задана точка лежить на стороні грані, вона не вважається вершиною, а якщо декілька таких точок лежать в одній вершині, їх треба вважати за одну вершину.
Ліміт часу 5 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
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
Вихідні дані #1
Case #1:
3: 5
5: 1
Case #2:
3: 4