K-Means Clustering for Plant Preferences

You are given a set of plants, each represented by three numerical preferences: water, light, and soil. Your task is to cluster these plants into k groups using the k-means clustering algorithm.

In the algorithm, you will use the Euclidean distance to measure the similarity between the plants. The Euclidean distance between two points \(p_1 = (x_1,y_1,z_1)\) and \(p_2 = (x_2,y_2,z_2)\) is given by:

[ d(p_1, p_2) = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2} ]

Initially, the first k plants are chosen as the centroids. Then, the algorithm iterates between assigning each plant to the nearest centroid and updating each centroid to be the mean of all plants assigned to it. The process stops when the centroids do not change significantly.

After clustering, print each cluster in order. For each cluster, first output a line with Cluster i: (where i is the cluster number starting from 1), followed by each plant in that cluster on a separate line with its three preference values, separated by spaces.

inputFormat

The input is given via standard input (stdin) and has the following format:

1. An integer n representing the number of plants.
2. An integer k representing the number of clusters.
3. n lines, each containing three integers separated by spaces, representing the water, light, and soil preferences of a plant.

outputFormat

The output is printed to standard output (stdout). For each cluster (in order from 1 to k), print:

• A header line in the format: Cluster i:
• For each plant in the cluster, a line with its three preference values separated by single spaces.

Note that the order of clusters should correspond to the order determined by the algorithm.

## sample

6
2
3 5 1
10 10 10
2 3 2
11 11 10
4 5 1
9 9 9

Cluster 1:
3 5 1
2 3 2
4 5 1
Cluster 2:
10 10 10
11 11 10
9 9 9

</p>