#include "stdio.h"
#include "stdlib.h"

#define theta 0.2

typedef struct Person
{
	float m_fweight;
	float m_fheight;
	int  m_nCenterflag;
} Person;

int ComputeVNum(FILE* fp)
{

	char mid;
	int cap=0;
	while(!feof(fp)) 
	{ 
		mid=fgetc(fp); 
		if(mid=='\n') cap++; 
	} 
	return cap;	

}
float ComputeDistance(Person p1,Person p2)
{
	float distance;
	distance=(p1.m_fweight-p2.m_fweight)*(p1.m_fweight-p2.m_fweight)+(p1.m_fheight-p2.m_fheight)*(p1.m_fheight-p2.m_fheight);
	return distance;
}

void main()
{
	FILE* f;
	if((f=fopen("data.txt","r"))==NULL)
	{
		printf("file cann't open");
		exit(0);
	}

    int i;
	int PersonNum=ComputeVNum(f);

	Person* m_Data=new Person[PersonNum];
	Person* m_Center=new Person[PersonNum];

	for(i=0;i<PersonNum;i++)
		m_Data[i].m_nCenterflag=0;
	
	int  m_nheight;
	int  m_nweight;
	fseek(f,0,0);
	for(i=0;i<PersonNum;i++)
	{
		fscanf(f,"%d %d\n",&m_nheight,&m_nweight);

		m_Data[i].m_fheight=float(m_nheight);
		m_Data[i].m_fweight=float(m_nweight);
		
	}
	fclose(f);
	m_Center[0]=m_Data[0];
	m_Data[0].m_nCenterflag=1;

	float m_fMaxD=0;
	float m_fMaxDistance;
	float m_fPatternDistance;
	int m_nIndex=0;
	for(i=1;i<PersonNum;i++)
	{
		m_fPatternDistance=ComputeDistance(m_Center[0],m_Data[i]);

		if(m_fPatternDistance>m_fMaxD)
		{
			m_fMaxD=m_fPatternDistance;
			m_nIndex=i;
		}
	}

	m_fMaxDistance=m_fMaxD;

	m_Center[1]=m_Data[m_nIndex];
	m_Data[m_nIndex].m_nCenterflag=1;
	int CenterNum=2;

	float m_fminD=100000000;

	m_fMaxD=0;
	while(1)
	{
		for(i=0;i<PersonNum;i++)
		{
			if(m_Data[i].m_nCenterflag==1)
				continue;
			for(int j=0;j<CenterNum;j++)
			{
				m_fPatternDistance=ComputeDistance(m_Center[j],m_Data[i]);
				if(m_fminD>m_fPatternDistance)
					m_fminD=m_fPatternDistance;
			}
			if(m_fMaxD<m_fminD)
			{
				m_fMaxD=m_fminD;
				m_nIndex=i;
			}	
		}
		if(m_fMaxD>theta*m_fMaxDistance)
		{
			CenterNum++;
			m_Center[CenterNum]=m_Data[m_nIndex];
		}
		else
			break;
	}

	
	for(i=0;i<PersonNum;i++)
	{
		m_fminD=1000000.0;
		for(int j=0;j<CenterNum;j++)
		{
			m_fPatternDistance=ComputeDistance(m_Center[j],m_Data[i]);
				if(m_fminD>m_fPatternDistance)
				{
					m_fminD=m_fPatternDistance;
					m_Data[i].m_nCenterflag=j;
				}
		}
	}

	for(i=0;i<CenterNum;i++)
	{
		printf("the %d class include:\n\n",i);
		for(int j=0;j<PersonNum;j++)
		{
			if(m_Data[j].m_nCenterflag==i)
				printf("%f	%f\n\n",m_Data[j].m_fheight,m_Data[j].m_fweight);
		}

	}
	
	

}