---
tags: 程式碼
---
# K-means

#include <bits/stdc++.h>
#define Point pair<double, double>
#define x first
#define y second
#define p first
#define c second
using namespace std;

/*
Specify the number K of clusters to assign.
Randomly initialize K centroids.
repeat
        expectation: Assign each point to its closeset centroid
        maximization: Compute the new centroid of each cluster.
until - Thecentroid positions do not change.
*/

double dist(Point A, Point B) {
        double dx = A.x - B.x;
        double dy = A.y - B.y;
        return sqrt(dx*dx+dy*dy);
}

void point_add(Point &A, Point B) {
        A.x += B.x;
        A.y += B.y;
}

void solve() {
        int n, k;
        char _ch;
        cin >> n >> k;
        vector< pair<Point, int> > point_list(n);
        vector< Point > centroid(k);
        for(auto &it: point_list) cin >> it.p.x >> _ch >>  it.p.y;
        for(auto &it: centroid) it = point_list[rand()%n].p;

        bool is_change = true;
        while(is_change) {
                is_change = false;
                vector< Point > sum(k);
                vector< int > count(k, 0);
                for(auto &it: point_list) {
                        for(int i = 0; i < k; i++) 
                                if(it.c != i && 
                                dist(it.p, centroid[it.c]) > dist(it.p, centroid[i])) 
                                        is_change = true, it.y = i;
                        point_add(sum[it.c], it.p); 
                        count[it.c]++;

                }
                for(int i = 0; i < k; i++) {
                        centroid[i].x = sum[i].x / (1e-7+count[i]);
                        centroid[i].y = sum[i].y / (1e-7+count[i]);
                }
        }
        for(auto it: point_list) cout << it.y << endl;
}


int main() {
        int t = 1;
        //cin >> t;
        while(t--) solve();
        return 0;
}