# 2021s K-means法

import math

def clustering(N, K, points):
    # --- 初期設定 ---
    MaxCount = 100  # 無限ループ防止用の最大回数 [cite: 53, 54, 57]
    
    # 本来はランダムに選ぶが、設問の例に合わせて P2 と P5 を初期コアに設定 [cite: 16]
    # core[t] はコア番号 t の点の番号 m を格納する 
    core = {1: 2, 2: 5} 
    
    # 点 s が所属するクラスタ番号を格納する配列 
    cluster = [0] * (N + 1)
    
    # 重心の座標を格納する配列 
    coordinate_x = [0.0] * (K + 1)
    coordinate_y = [0.0] * (K + 1)

    # 距離計算関数 (手順2より) [cite: 7]
    def get_dist(p1, p2):
        return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

    # --- クラスタを決定 (1回目) --- [cite: 58]
    for s in range(1, N + 1):
        data_length = [0.0] * (K + 1)
        for t in range(1, K + 1):
            # 点 Ps とコア番号 t (点 P_core[t]) との距離を計算 [cite: 60]
            data_length[t] = get_dist(points[s], points[core[t]])
        
        # 距離が最小の添字（クラスタ番号）を格納 [cite: 61]
        # 距離が等しい場合は番号が小さい方を返す [cite: 7, 44]
        min_val = min(data_length[1:])
        cluster[s] = data_length.index(min_val, 1)

    # --- クラスタの見直しループ --- [cite: 63]
    for p in range(1, MaxCount + 1):
        flag = 0  # [ウ] 重心の移動を判定するフラグ [cite: 44, 85]
        
        # 重心の計算 (手順3) [cite: 8, 69]
        for t in range(1, K + 1):
            # クラスタ t に属する点を探し、平均（重心）を求める
            members = [points[s] for s in range(1, N + 1) if cluster[s] == t]
            if members:
                new_gx = sum(m[0] for m in members) / len(members)
                new_gy = sum(m[1] for m in members) / len(members)
                
                # 2回目以降、重心が変わったかチェック [cite: 80, 82]
                if p > 1:
                    if new_gx != coordinate_x[t] or new_gy != coordinate_y[t]:
                        flag = 1
                
                # 重心の座標を更新 [cite: 70, 72, 83, 84]
                coordinate_x[t] = new_gx
                coordinate_y[t] = new_gy

        # [エ] 重心の座標が変わらなくなったら終了 [cite: 10, 90, 94]
        if p > 1 and flag == 0:
            print(f"分類完了：第 {p} 回目のループで収束しました。")
            break

        # [オ] 各点と新しい重心との距離を計算し、所属を更新する [cite: 9, 97-104]
        for s in range(1, N + 1):
            grav_length = [0.0] * (K + 1)
            for t in range(1, K + 1):
                # 点 Ps と重心 Gt との距離を計算
                grav_length[t] = get_dist(points[s], (coordinate_x[t], coordinate_y[t]))
            
            # 最も近い重心の番号を次の所属クラスタ番号とする
            min_val = min(grav_length[1:])
            cluster[s] = grav_length.index(min_val, 1)

    return cluster, coordinate_x, coordinate_y

# --- データ入力と実行 ---
# 点の座標データ (P1~P7) [cite: 12]
data_points = {
    1: (1, 0), 2: (2, 1), 3: (4, 1), 4: (1.5, 2),
    5: (1, 3), 6: (2, 3), 7: (4, 3)
}

final_clusters, g_x, g_y = clustering(7, 2, data_points)

# 結果表示
print("-" * 30)
for s in range(1, 8):
    print(f"点 P{s}: クラスタ {final_clusters[s]}")