<PREV Problem:
NEXT>
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

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 54.80.60.91