Loading [MathJax]/jax/output/CommonHTML/jax.js

Problem C. Clustering of triangles

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,,(N1).

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,

2N105.

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.077s 0.014s 13