機械学習/k-mean/ソース - AIとか機械学習とか、それらのコンテストとかのwiki

#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <bitset>
#include <fstream>
#include <sstream>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <sys/time.h>
using namespace std;
#define li        long long int
#define rep(i,to) for(li i=0;i<((li)(to));++i)
#define pb        push_back
#define sz(v)     ((li)(v).size())
#define bit(n)    (1ll<<(li)(n))
#define all(vec)  (vec).begin(),(vec).end()
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define MP        make_pair
#define F         first
#define S         second
 
 
#define MAX 40000
double X[4]={0,0,10,10};
double Y[4]={0,10,0,10};
li cluster[MAX];
pair<double,double> center[4];
pair<double,double> points[MAX];
 
int main(){
	rep(i,MAX) points[i]=MP(rand()%7-3.0+X[i%4],rand()%7-3.0+Y[i%4]);
	rep(i,4) center[i]=MP(rand(),rand());
	rep(i,MAX) cluster[i]=i%4;
	bool updated=true;
	while(updated){
		updated=false;
		rep(i,4){
			double sumX=0,sumY=0;
			li cnt=0;
			rep(j,MAX)if(cluster[j]==i){
				sumX+=points[j].F;
				sumY+=points[j].S;
				cnt++;
			}
			if(cnt==0) continue;
			center[i]=MP(sumX/cnt,sumY/cnt);
		}
		rep(i,MAX){
			pair<double,li> best=MP(1e100,-1);
			rep(j,4){
				double dx=points[i].F-center[j].F;
				double dy=points[i].S-center[j].S;
				best=min(best,MP(hypot(dx,dy),j));
			}
			if(cluster[i]!=best.S) updated=true;
			cluster[i]=best.S;
		}
	}
	rep(i,4){
		cout<<center[i].F<<" "<<center[i].S<<endl;
		rep(j,MAX)if(cluster[j]==i){
//			cout<<"  "<<points[j].F<<" "<<points[j].S<<endl;
		}
	}
}