Problem Statement

Implement the K-Means++ centroid initialization algorithm and compute the WCSS (Within-Cluster Sum of Squares) with the chosen centroids.

Algorithm:

1. Set numpy.random.seed(seed).
2. Choose the first centroid uniformly at random from the data points.
3. For each subsequent centroid: compute the squared distance from each point to the nearest already-chosen centroid, use these as sampling probabilities, and sample one point.
4. After selecting k centroids, assign each point to the nearest centroid and compute WCSS = sum of squared distances from each point to its assigned centroid.

Function signature:

def kmeans_plusplus(X: list, k: int, seed: int) -> tuple:
    # returns (indices, wcss)
    # indices: list of k centroid indices (in the order chosen)
    # wcss: float

Input Format

Line 1: n k seed — number of points, number of clusters, random seed
Lines 2..n+1: space-separated floats — coordinates of each point

Output Format

Line 1: space-separated sorted centroid indices
Line 2: WCSS value (10 significant figures)

Example

Input:

6 2 42
0.0 0.0
1.0 0.0
0.0 1.0
10.0 10.0
10.0 11.0
11.0 10.0

Output:

2 3
5

Notes

• Use numpy.random.randint for the first centroid and numpy.random.choice with probabilities for subsequent ones.
• Centroids are output sorted by index, but selected in order (first pick, then D² sampling).
• K-Means++ provides a better-spread initialization than purely random selection.