|Online MIPT programming contest||РУССКИЙ|
Time limit = 20 second(s)
Memory limit = 128000The 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, i ≠ j, 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.
2 1 1 1 3 -3 3
1 1 1
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
2 1 1 2 2 2 1
4 August, 2003
© acm.mipt DevGroup
The page was generated in 180ms