//采用課件中康立山等人的改進方法：
//			初始溫度t0=28000；
//			在每個溫度下采用固定的迭代次數，Lk=400n，n為城市數；
//			溫度的衰減系數＝0.96，即tk+1=0.96*tk；
//			算法的停止準則為：當相鄰10個溫度得到的解無任何變化時算法停止。 
//初始城市序列為: 1, 2, 3, ..., n
#include<iostream>
#include<cmath>
#include<string>
#include<fstream>
#include<ctime>
#include<cstdlib>
using namespace std;
#define e 2.718281828459
#define max	100
int n;						//城市總數
double t = 28000;				//溫度
int k;					//每個溫度下的迭代次數
double d = 0.97;				//衰減系數
struct City
{
	double x;
	double y;
	string name;
};

City cityArray[max];
City tempArray[max];			//用于城市互換時
double getDis();				//得到當前序列的總距離
double getDis(int, int);		//得到兩個城市間的距離
void print();					//輸出當前城市序列和路徑距離
int main()
{
	//infile
	string fileName;
	cin>>fileName;
	ifstream infile;
	infile.open(fileName.c_str());
	if (!infile) {
		cerr<<"infile error!"<<endl;
		return -1;
	}
	infile>>n;
	k = 400*n;
	for (int i=0; i<n; i++) {
		City newCity;
		infile>>newCity.name>>newCity.x>>newCity.y;
		cityArray[i] = newCity;
	}
	infile.close();

	//開始模擬退火
	double formerDis[10] = {0};
	formerDis[9] = getDis();
	double currentDis = 0;
	double delta = 0.0;
	bool flag;			//是否終止標志
	srand(19871019);
	while(true)
	{
		flag = true;
		for (int i=0; i<10; i++) {
			if (formerDis[i] != currentDis) {
				flag = false;
				break;
			}
		}
		if (flag)					//連續10個值都相同，退出
			break;
		for (int i=0; i<9; i++)
			formerDis[i] = formerDis[i+1];
		formerDis[9] = currentDis;
		int count = 0;
		while(count < k)
		{
			//從領域中隨機取一個解
			int first = (int)(((float)rand()/RAND_MAX)*n);
			int second = (int)(((float)rand()/RAND_MAX)*n);
			if (first > second) {
				int temp = first;
				first = second;
				second = temp;
			}
			delta = getDis(first, second - 1) + getDis(first + 1, second)
					- getDis(first, first + 1) - getDis(second - 1, second);
			if (delta < 0 || pow(e, -delta/t) > rand()/RAND_MAX) {			//進行交換
				for (int i = first+1; i<=second-1; i++)
					tempArray[i] = cityArray[i];
				for (int i = first+1; i<=second-1; i++)
					cityArray[i] = tempArray[first+second-i];
				currentDis = getDis();
				//print();
			}
			count++;
		}
		t *= d;
		currentDis = getDis();
		cout<<"-----------------------------------"<<endl;
		cout<<"當前溫度: "<<t<<endl;
		print();
	}
	cout<<"結果為："<<endl;
	print();
	return 0;
}
double getDis()
{
	double dis = 0.0;
	for (int i=0; i<n; i++)
	{
		dis += getDis(i, i+1);
	}
	return dis;
}
double getDis(int i, int j)
{
	if (i > n-1)
		i -= n;
	if (j > n-1)
		j -= n;
	return sqrt(pow((cityArray[i].x - cityArray[j].x),2.0)
			+ pow((cityArray[i].y - cityArray[j].y), 2.0));
}
void print()
{
	cout<<"城市序列: (";
	for (int i=0; i<n-1; i++)
		cout<<cityArray[i].name<<",";
	cout<<cityArray[n-1].name<<")";
	cout<<"路徑距離:"<<getDis()<<endl;
}