Time limit 2000/5000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.
K-Means
K-Means is one of the commonly used algorithms
in Data Mining. It’s an unsupervised learning
method. It partitions the given instances into
the given number of clusters where each instance
belongs to the cluster with the nearest distance.
When calculating K-Means,
- The first K data are assigned as K centers
- First item is assigned as first center, etc.
- Then the distances of all instances to all K
centers are calculated.
- And every instance is assigned to its nearest
center.
- According to newly assigned instances, the
coordinates of each center is calculated again.
- The operation continues from step 2 as far as
the difference between previous and this total
distances is greater than eps (e.g. 1e-4).
Question:
Write a program that reads 3D information for n
instances, and print the coordinates of k centers.
Input specification
You will be given two integers in the beginning:
the number of instances (n) and the number of
clusters (k) where 1 ≤ n ≤10,000
and 1 ≤ k ≤ 10. Then the following n lines
will contain 3 integers (x, y and z coordinates)
and a class information.
Output specification
Show 3 floating point numbers with 2 digits
precision in k lines.
Sample Input I
11 3
-2 5 0
5 8 0
-2 5 0
4 -3 0
-4 6 0
3 8 0
5 -4 0
-5 3 0
-7 6 0
6 -2 0
5 -5 0
|
Sample Output I
5 -3.5 0
4 8 0
-4 5 0
|
Для отправки решений необходимо выполнить вход.
|