//20個點(diǎn)，分兩類
#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;

#define N_CLASS 4	//分類數(shù)
#define N_POINT 20	//點(diǎn)的個數(shù)
#define VERY_BIG 999999999.9	//超過程序中可能遇到的所有數(shù)的一個值，也就是無窮大

struct Point{
	double x;
	double y;
};
struct Index{
	int in_class;//哪一類
	int in_length;//類大小
};
//求size個點(diǎn)的新聚心
void Average(struct Point *c, int size, struct Point *p);
//比較兩個長度相同的向量是否所有對應(yīng)元素相等
bool SameVector(vector<Point> &y, vector<Point> &z, int size);
//比較兩個浮點(diǎn)值是否相等
bool DoubleCompare(double a, double b);

int main(void)
{
	vector<Point> p;//點(diǎn)向量
	vector<Point> z;//聚心向量
	vector<Point> y;//備份聚心向量
	Point c[N_CLASS][N_POINT];//20個點(diǎn)分兩類
	Index index[N_CLASS];
	int i=0, j=0;
	double d;

	cout << "請輸入 "<< N_POINT << " 個點(diǎn)"<< "進(jìn)行聚類分析，將分成 " << N_CLASS << " 個類" <<endl;
	Point temp;
	for(i=0;i<N_POINT;i++){
		cin >> temp.x >> temp.y;
		p.push_back(temp);
		if(i<N_CLASS)//選擇N_CLASS個聚心
		{
			z.push_back(temp);
		}
	}
	int k=0;
	int min_index, class_index;	
	do{
		for(i=0;i<N_CLASS;i++){
			index[i].in_class = i;
			index[i].in_length = 0;
		}
		y.clear();//初始化

		for(i=0;i<N_POINT;i++)	
		{
			double min_d=VERY_BIG;
			for(j=0;j<N_CLASS;j++)	
			{
				d = sqrt( (p[i].x - z[j].x)*(p[i].x - z[j].x) + (p[i].y - z[j].y)*(p[i].y - z[j].y) );
				if(d < min_d)
				{
					min_d = d;
					min_index = i;
					class_index = j;//保留最小的
				}
			}
			//劃分類,將min_index點(diǎn)話奮進(jìn)class_index類
			c[ class_index ][ index[class_index].in_length ].x = p[min_index].x;
			c[ class_index ][ index[class_index].in_length ].y = p[min_index].y;
			index[class_index].in_length++;			
		}
		//保存舊聚心
		for(vector<Point>::iterator itr_z=z.begin();itr_z!=z.end();itr_z++)
			y.push_back(*itr_z);

		//求新聚心
		for(i=0;i<N_CLASS;i++)
		{
			Average(c[i], index[i].in_length, &z[i]);
		}
		k++;
//		if(k==100)
//			break;
	}while(!SameVector(y, z, y.size()));

	cout<<"分類結(jié)果是:"<<endl;
	for(i=0;i<N_CLASS;i++)
	{
		cout<< "以"<< "( "<<z[i].x << " , " << z[i].y <<" )"<<"為聚心"<< "有以下的點(diǎn)"<<endl;
		for(j=0;j<index[i].in_length;j++)
			cout << "( " << c[i][j].x << " , " << c[i][j].y << " )" << endl;
	}
	cout << "共迭代"<< k <<"次"<< endl;
	return 0;
}
//求size個點(diǎn)的新聚心
void Average(struct Point *c, int size, struct Point *p)
{
	int i;
	for(i=0;i<size;i++)
	{
		p->x+=c[i].x;
		p->y+=c[i].y;
	}
	p->x /= size;
	p->y /= size;
}

bool SameVector(vector<Point> &y, vector<Point> &z, int size)
{
	int i;
	for(i=0;i<size;i++)
	{
		if(!DoubleCompare(y[i].x, z[i].x) || !DoubleCompare(y[i].y, z[i].y) )
			return false;
	}
	return true;
}

bool DoubleCompare(double a, double b)
{
	if( abs(a - b) < 0.00001 )
		return true;
	return false;
}