K-Means Clustering

You are given a set of N points in an M-dimensional space and an integer K. Your task is to implement the K-Means clustering algorithm with a maximum of 100 iterations.

The algorithm works as follows:

• Initialization: Randomly select K distinct points from the data set as the initial centroids.
• Assignment: Assign each point to the closest centroid using the Euclidean distance.
• Update: Recalculate the centroids as the mean of all points assigned to each cluster.
• Convergence: Repeat steps 2 and 3 until no change occurs in centroids (or until the maximum number of iterations is reached).

To ensure reproducibility across different runs, you must fix the random seed to 42.

The program reads the input from stdin and prints results to stdout.

inputFormat

The input is read from stdin and has the following format:

The first line contains three integers N, M and K, where N is the number of data points, M is the dimension of each data point, and K is the number of clusters.

This is followed by N lines, each containing M space-separated real numbers representing the coordinates of a point.

outputFormat

The output should be printed to stdout and must include:

1. K lines, each containing the coordinates of a centroid rounded to 4 decimal places (coordinates separated by a single space).
2. A single line containing N space-separated integers (0-indexed) representing the cluster assignment for each input point in the original order.## sample

4 2 2
1 2
1 4
3 4
5 7

1.6667 3.3333
5.0000 7.0000
0 0 0 1