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.
UserDateAttemptTimeCMSC
tourist`23 mar 2009`Kylix8102.16489
WsemirZ`29 jul 2008`Kylix2102.19615
defrager`24 mar 2009`C++501.87656
greck`31 mar 2008`Ruby3199.08892
DAV`04 sep 2009`C++1603.00972
abortmozga.ru`26 aug 2009`C++902.93981
Algeran`08 apr 2010`C++100.34991
Algeran`08 apr 2010`C++200.34991
Lu`08 apr 2010`C++600.34991
TonyZH`22 apr 2010`C++500.34993
mishik`20 apr 2008`C++1505.61993
mishik`20 apr 2008`C++1405.601012
greck`10 apr 2008`C++400.411022
mishik`20 apr 2008`C++1305.571042
 C++ 16 FPC 3 Kylix 2 Java 1 Ruby 1
` >  >  >  >  >  >  >  >  >  > `

## 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 200ms