#include<iostream.h>
#include<fstream.h>
#include<math.h>
#include<stdlib.h>

struct location{
	double x;
	double y;
};

struct edge{
	location l1;
	location l2;
};

char * STOP='\0';
ifstream info;
int patient_no;
location * home;
int nurse_no;
location *start;
edge * path;
int max_serve_no;
int pUnvisited;
int pVisitEdge=0;
int last_edge=0;
int current_nurse=0;
double totalLength[100];

double Distance(location l1, location l2)
{
	return sqrt((l1.x-l2.x)*(l1.x-l2.x)+(l1.y-l2.y)*(l1.y-l2.y));
}

double H(location l, edge e)
{
	return Distance(e.l1,l)+Distance(l,e.l2)-Distance(e.l1,e.l2);
}

int main(int argc, char * argv[])
{
	if(argc!=2)
	{
		cout<<"please imput information file:\n";
		return 1;
	}

	//read location
	info.open(argv[1]);
	
	int i=0;
	int j=0;
	char line[100];
	char temp[10];

	//read patient number
	info.getline(line,100);
	while(line[i]==' ')i++;
	while(line[i]!='\0')temp[j++]=line[i++];
	temp[j]='\0';
	patient_no=strtol(temp,&STOP,10);

	pUnvisited=patient_no;
	home=new location[patient_no];
	path=new edge[patient_no+1];

	//read each patient
	for(int k=0;k<patient_no;k++)
	{
		//read location
		info.getline(line,100);
		i=0;
		j=0;
		while(line[i]==' ')i++;
		while(line[i]!=',')temp[j++]=line[i++];
		temp[j]='\0';
		home[k].x=strtol(temp,&STOP,10);
		j=0;
		i++;
		while(line[i]==' ')i++;
		while(line[i]!='\0')temp[j++]=line[i++];
		temp[j]='\0';
		home[k].y=strtol(temp,&STOP,10);
	}

	//read nurse number
	info.getline(line,100);
	i=0;
	j=0;
	while(line[2]==' ')i++;
	while(line[i]!='\0')temp[j++]=line[i++];
	temp[j]='\0';
	nurse_no=strtol(temp,&STOP,10);
	start = new location[nurse_no];
	for(int x=0;i<nurse_no;i++)totalLength[x]=0.0;

	//read nurse
	for(k=0;k<nurse_no;k++)
	{
		//read location
		info.getline(line,100);
		i=0;
		j=0;
		while(line[i]==' ')i++;
		while(line[i]!=',')temp[j++]=line[i++];
		temp[j]='\0';
		start[k].x=strtol(temp,&STOP,10);
		j=0;
		i++;
		while(line[i]==' ')i++;
		while(line[i]!='\0')temp[j++]=line[i++];
		temp[j]='\0';
		start[k].y=strtol(temp,&STOP,10);
	}

	//read maximum serve number
    info.getline(line,100);
	i=0;
	j=0;
	while(line[i]==' ')i++;
	while(line[i]!='\0')temp[j++]=line[i++];
	temp[j]='\0';
	max_serve_no=strtol(temp,&STOP,10);

	//schedule
	int selectedNode;
	int selectedEdge;
    double MinH=1000000.0;

	while(pUnvisited)
	{
		//assign a nurse
		pVisitEdge=0;
		last_edge=0;
		cout<<"nurse "<<current_nurse<<':'<<'\n';
		cout<<'\n';

		path[0].l1.x=start[current_nurse].x;
		path[0].l1.y=start[current_nurse].y;
	
		double MinD=Distance(start[current_nurse],home[0]);
		int selectF=0;

		for(i=1;i<pUnvisited;i++)
		{
			if(Distance(start[current_nurse],home[i])<MinD)
			{
				MinD=Distance(start[current_nurse],home[i]);
				selectF=i;
			}
		}


		totalLength[current_nurse]+=MinD;
		path[0].l2.x=home[selectF].x;
		path[0].l2.y=home[selectF].y;
		last_edge=pVisitEdge;
		pVisitEdge++;

		for(i=selectF;i<pUnvisited-1;i++)
		{
			home[i].x=home[i+1].x;
			home[i].y=home[i+1].y;
		}
		pUnvisited--;

		for(int l=0;l<max_serve_no-1;l++)
		{
			if(!pUnvisited)break;

			MinH=100000.0;

			//search
			for(i=0;i<pUnvisited;i++)
			{
				for(j=0;j<pVisitEdge;j++)
				{
					if(H(home[i],path[j])<MinH)
					{
						MinH=H(home[i],path[j]);
						selectedNode=i;
						selectedEdge=j;
					}
				}
			}

			if(selectedEdge==last_edge)last_edge=pVisitEdge;

			totalLength[current_nurse]+=MinH;
			//update
			path[pVisitEdge].l1.x  =home[selectedNode].x;
			path[pVisitEdge].l1.y  =home[selectedNode].y;
			path[pVisitEdge].l2.x  =path[selectedEdge].l2.x;
			path[pVisitEdge].l2.y  =path[selectedEdge].l2.y;
			path[selectedEdge].l2.x=home[selectedNode].x;
			path[selectedEdge].l2.y=home[selectedNode].y;
			pVisitEdge++;

			for(i=selectedNode;i<pUnvisited-1;i++)
			{
				home[i].x=home[i+1].x;
				home[i].y=home[i+1].y;
			}

			pUnvisited--;
		}

		path[pVisitEdge].l1.x=path[last_edge].l2.x;
		path[pVisitEdge].l1.y=path[last_edge].l2.y;
		path[pVisitEdge].l2.x=start[current_nurse].x;
		path[pVisitEdge].l2.y=start[current_nurse].y;

		totalLength[current_nurse]+=Distance(path[pVisitEdge].l1,path[pVisitEdge].l2);

		pVisitEdge++;

		for(int y=0;y<pVisitEdge;y++)cout<<'('<<path[y].l1.x<<','<<path[y].l1.y<<')'<<'\t'<<'('<<path[y].l2.x<<','<<path[y].l2.y<<')'<<'\n';

		cout<<'\n';
		cout<<"total travel length is: "<<totalLength[current_nurse]<<'\n';
		cout<<'\n';
		current_nurse++;
	}

	return 0;	
}