#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

struct Point {
double abs;
double ord;
};
typedef struct Point point;

point* echantillon(point* donnees, int N, int m){

    for (int i=0;i<N;i++){
        int indice = rand()%(i+1); 
        if (indice<m){
            point save=donnees[indice];
            donnees[indice]=donnees[i];
            donnees[i]=save;
        }
    }
    point* res=malloc(m*sizeof(point));
    for (int i=0;i<m;i++){
        res[i]=donnees[i];
    }
    return res;

}
double distance (point x, point y){
    return ((x.abs-y.abs)*(x.abs-y.abs)+(x.ord-y.ord)*(x.ord-y.ord));
}

int plus_proche (point x, point* bary, int m){
    int res=0;
    double d = distance (x,bary[0]);
    for (int i=1;i<m;i++){
        double d_a=distance(x,bary[i]);
        if (d_a<d){
            d=d_a;
            res=i;
        }
    }
    return res;
}

bool modif_classe(point* donnees, point* bary, int* classe, int N, int m){
    bool res=false;
    for (int i=0;i<N;i++){
        int indice_classe = plus_proche(donnees[i],bary,m);
        if (classe[i]!=indice_classe){
            classe[i]=indice_classe;
            res=true;
        }
    }
    return res;
}

void modif_bary(point* donnees, point* bary, int* classe, int N, int m){
    int* nb =malloc(m*sizeof(int));
    for (int i=0;i<m;i++){
        bary[i].abs=0; bary[i].ord=0;nb[i]=0;
    }
    for (int i=0;i<N;i++){
        bary[classe[i]].abs+=donnees[i].abs;
        bary[classe[i]].ord+=donnees[i].ord;
        nb[classe[i]]+=1;
    }
    for (int i=0;i<m;i++){
        if (nb[i]!=0){
        bary[i].abs/=nb[i];
        bary[i].ord/=nb[i];}
    }
    free(nb);

}

int* k_moyennes(point* donnees, int N, int m, int itermax){
    point* bary=echantillon(donnees,N,m);
    int* classe = malloc(N*sizeof(int));
    int cpt =0;
    while(modif_classe(donnees,bary,classe,N,m)&&cpt<itermax){
        modif_bary(donnees,bary,classe,N,m);
        cpt++;
    }free(bary);
    return classe;
}
int main(){

    point* test=malloc(10*sizeof(point));
    for (int i=0;i<10;i++){
        test[i].abs= rand()%15;
        test[i].ord = rand()%15;
    }

    
    int* res =k_moyennes(test,10,3,1);
    for (int i=0;i<10;i++){
        printf("%d ", res[i]);
   }
}