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

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

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

Лимит времени 5 секунд
Лимит использования памяти 64 MiB

Дано множество точек в трёхмерном пространстве. Ваша задача состоит в том, чтобы посчитать количество граней с k вершинами выпуклого многогранника минимального объёма, содержащего все данные точки.

Входные данные

Первая строка ввода содержит количество тестов T (1 ≤ T ≤ 100). Первая строка каждого теста содержит количество точек в множестве – N (4 ≤ N ≤ 30). Далее следуют N строк, каждая из которых содержит 3 целых числа: X, Y, Z (–1000 ≤ X, Y, Z ≤ 1000) – координаты точек. Некоторые точки могут иметь одни и те же координаты! Гарантируется, что любой выпуклый многогранник, содержащий все данные точки, будет иметь положительный объём.

Выходные данные

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

Пример

Входные данные #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