/**
C均值聚类算法的C语言实现
Author：AnranWu
Date:2020/11/25 
*/ 
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn=1e6+50;
const double eps=1e-2;

struct node{
	double x=0,y=0;
}a[maxn],b[maxn],sum[maxn];

int belong[maxn],cnt[maxn];

double dis(node a,node b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int main(){
	int c,n;
	printf("请输入需要将模式分为的类别数 c ："); 
	scanf("%d",&c);
	printf("请输入模式总数 n ："); 
	scanf("%d",&n);//输入需要聚类的模式数 
	printf("请输入各模式的两个特征点 ：\n"); 
	for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);//输入每个模式的两个特征 
	for(int i=1;i<=c;i++)b[i]=a[i];//选定初始的c个聚类中心 
	int ans=0;//ans表示与上次聚类中心一致的聚类中心点数量，当所有聚类中心均不发生改变时循环结束 
	while(ans<c){
		memset(cnt,0,sizeof(cnt));//cnt记录每一个类别有多少个模式属于该类 
		for(int i=1;i<=n;i++){
			double minn=4e18;//计算该模式到每一个聚类中心的距离
			int mini=0;
			for(int j=1;j<=c;j++){
				double dis_to_center=dis(a[i],b[j]);
				if(dis(a[i],b[j])<minn){
					minn=dis_to_center;
					mini=j;
				}
			}
			belong[i]=mini;//选择距离最小的一个类加入该类 
			cnt[mini]++;//更新该类中模式的数量 
		}
		for(int i=1;i<=c;i++)sum[i].x=0,sum[i].y=0;
		for(int i=1;i<=n;i++){
			sum[belong[i]].x+=a[i].x;
			sum[belong[i]].y+=a[i].y;//计算新的聚类中心 
		}
		ans=0;
		for(int i=1;i<=c;i++){
			sum[i].x/=cnt[i];
			sum[i].y/=cnt[i];
			//判断该聚类中心是否发生变化,eps控制容差值 
			if((fabs(sum[i].x-b[i].x)<eps)&&(fabs(sum[i].y-b[i].y)<eps))ans++;
			b[i].x=sum[i].x; 
			b[i].y=sum[i].y;//更新聚类中心 
		}
	}
	printf("C均值聚类算法已经完成！\nc个类中心分别为\n");
	for(int i=1;i<=c;i++){
		printf("第%d类的聚类中心的两个特征值分别为 %.2lf %.2lf\n",b[i].x,b[i].y); 
	}
	for(int i=1;i<=c;i++){
		printf("属于第%d类的点有：\n"); 
		for(int j=1;j<=n;j++){
			if(belong[j]==i)printf("%d号点 %.2lf %.2lf\n",j,a[j].x,a[j].y);
		}
		putchar(10);
	}
}

/*
测试数据 #1
2
20
0 0
1 0
0 1
1 1
2 1
1 2
2 2
3 2
6 6
7 6
8 6
6 7
7 7
8 7
9 7
7 8
8 8
9 8
8 9
9 9
*/