HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Ad-Hoc > problem:


50498 - K-Means

Guest
• Review clarifications (1)

Section problems

• 50375 - Area of Circles
• 50393 - Palindromic Numbers
• 50396 - Cinema Tickets - 1
• 50325 - How much time passed?
• 50366 - Student Averages (2 Grades)
• 50406 - Draw Pattern 178
• 50416 - Placing Dominoes on Chess...
• 50477 - Character Pyramids
• 50498 - K-Means
• 50505 - kht Puzzle
• 50346 - The Biggest Date
• 50512 - Coding redundancy
• 50528 - Rock-Scissors-Paper
• 50493 - n-digit kth Prime Number
• 50520 - Filling a Matrix Randomly
• 50357 - Convert Euros into Dollars
• 50355 - Bills of City Water Company

Feedback

If you notice incorrect translations in Contester, please let author know.

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,

  1. The first K data are assigned as K centers
    • First item is assigned as first center, etc.
  2. Then the distances of all instances to all K centers are calculated.
  3. And every instance is assigned to its nearest center.
  4. According to newly assigned instances, the coordinates of each center is calculated again.
  5. 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


Для отправки решений необходимо выполнить вход.

www.contester.ru