Solved by 22 users: greck, mishik, WsemirZ, dan, mazahaka, zloy_mipt, UdH-WiNGeR, ilyakor, tourist, defrager, abortmozga.ru, DAV, MIKseR, Algeran, Lu, TonyZH, ZhanibekDATBAEV, ripatti, Dest, vi002, regmar, avg79.
` <  <  <  <  <  <  <  <  <  < `

## Best clustering

Time limit = 20 second(s)

Memory limit = 128000

The Best Clusterization problem may be formulated in the following way:

The Problem: S — is a set of points in 3D Euclidean space. Split S into subsets(clasters) S1, S2, ..., SK, to minimize D:

Intersection of Si and Sj, ij, is empty set and union of all Si gives S. Si should contain more than one point, i.e. ni = |Si| ≥ 2.

Your program should solve the best clusterization problem in 3-dimentional space to some precision. That mean the less the value of D the better, and your program may get "Accepted" even if clusterization is not the best and D does not reach the absolute minimum.

There is critical value D0(t) for each test t. If clusterization found by your program has D less than D0(t), then test is successfully passed.

If your program passed all tests it is scored by

Input The first line of input contains N = |S| — number of points in S, N ≤ 5000. Next N lines contains coordinates xi, yi, zi of these points, real numbers, which absolute value less than 2 000 000.

Output The first line should contain number of found clusters C. Then N lines should follow. i-th line should contain cluster's identifier, which i-th point in the input belongs to. Identifiers of clusters are numbers 1,2, ..., C.

 Input#1```2 1 1 1 3 -3 3 ``` Output#1```1 1 1 ```
 Input#2```6 101.123 100.123 99.123 100.123 99.123 99.123 0.123 0.123 -0.123 0.123 -0.123 0.123 -0.123 0.123 0.123 100.321 100.123 100.123 ``` Output#2```2 1 1 2 2 2 1 ```

Author:
Voroztsov Artem
4 August, 2003

 © acm.mipt DevGroupThe page was generated in 180ms