## Problem C. Clustering of triangles ≡

• problems
• en ru
 Author: A. Baranov Time limit: 1 sec Input file: Standard input Memory limit: 512 Mb Output file: Standard output

### Statement

Let there be a set of triangles represented by 3-dimensional vertex coordinates.

You must determine all maximal subsets of triangles such that triangles of each set belong to a single plane.

### Input format

Input contains integer N, followed by 9 × N integers, representing vertex coordinates:

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

### Output format

Output must contain the number of subsets M, followed by M records of the following structure.

The number of triangles present in the set, followed by their indices in input (indexing starts at 0).

Both sets and triangles may be output in arbitrary order.

### Constraints

It is guaranteed that there are no degenerate (zero area) triangles in input.

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

2 ≤ N ≤ 105.

### Sample tests

No. Standard input Standard output
1
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


0.080s 0.012s 13