记录编号	52709	评测结果	AAAAAAAAAA
题目名称	6.线型网络	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2013-02-13 16:48:14	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<stack>
#include<iomanip>
#include<cstdlib>
#include<time.h>
using namespace std;
class point{
public:
	double x,y;
}p[38];
int n;
double ans=0xffffffff;
double leng[38][38]={0};
int list[38]={0};
int sum=0;
double dis(int a,int b){//a到b的距离
	double temp=(p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y);
	return sqrt(temp);
}
void swap(int &a,int &b){
	int temp;
	temp=a,a=b,b=temp;
}
void turn(int a,int b){//a<=b
	int i=a,j=b;
	while(i<=j){
		swap(list[i],list[j]);
		i++,j--;
	}
}
void makelist(void){
	int i,j;
	for(i=1;i<=n;i++){
		j=rand()%n+1;
		swap(list[i],list[j]);
	}
}
double count(void){
	double sum=0;
	for(int i=1;i<n;i++) sum+=leng[list[i]][list[i+1]];
	return sum;
}
void optimize(void){
	int i,j;
	for(i=1;i<=n-1;i++){
		for(j=i+1;j<=n;j++){
			if(leng[list[i-1]][list[i]]+leng[list[j]][list[j+1]]>leng[list[i-1]][list[j]]+leng[list[i]][list[j+1]]){
				turn(i,j);
			}
		}
	}
}
int main(){
	freopen("linec.in","r",stdin);
	freopen("linec.out","w",stdout);
	scanf("%d",&n);
	int i,j;
	for(i=1;i<=n;i++) list[i]=i;
	for(i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
	for(i=1;i<=n;i++){
		for(j=1;j<i;j++) leng[j][i]=leng[i][j]=dis(i,j);
	}
	double temp;
	for(i=0;i<1000;i++){
		makelist();
		optimize();
		temp=count();
		if(temp<ans) ans=temp;
	}
	cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans<<endl;
	return 0;
}