Задача AC. Clustering of triangles ≡

Условие

Имеется набор треугольников, заданных трехмерными координатами своих вершин.

Требуется сформировать все максимальные поднаборы из треугольников, такие что в каждом наборе все треугольники лежат в одной плоскости.

Формат входных данных

Входные данные содержат натуральное число N, за которым следует 9 × N целых чисел, задающих координаты вершин:

(X1i, Y1i, Z1i), (X2i, Y2i, Z2i), (X3i, Y3i, Z3i), где i = 0, 1, …, (N − 1).

Формат выходных данных

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

Сначала указывается число треугольников, включенных в набор, после чего следуют их номера во входных данных (нумерация начинается с 0).

Как наборы, так и треугольники в наборе можно перечислять в произвольном порядке.

Ограничения

Гарантируется, что в исходном наборе отсутствуют вырожденные треугольники (с нулевой площадью).

 − 1000 ≤ (Xki, Yki, Zki) ≤ 1000,

2 ≤ N ≤ 10⁵.

Примеры тестов

6

 166  -61 -108
-175  122  133
 -81   96   71

-100 -228  246
 -64   58  -68
 -85   12  -27

 131 -140 -101
  37 -114  -39
  72  -35  -46

 137 -186 -113
  84 -127  -70
  66   11  -34

-140 -143  121
 -45  -73   98
  34   31   25

-135 -170 -173
 -86   45 -252
  39  124   31

3

3 3 2 0
2 4 1
1 5