记录编号	246913	评测结果	AAAAAAAAAA
题目名称	线型网络	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.692 s
提交时间	2016-04-07 17:21:56	内存使用	0.29 MiB

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstring>
using std::cin;
using std::cout;
using std::swap;
using std::min;
const int MAXN=20+1;
struct P{
	double x,y;
}st[MAXN];
double ans=1000000,dt[MAXN][MAXN];
int table[MAXN],N;
inline void randp(){
	int a,b;
	for(int i=1;i<=100;i++) swap(table[rand()%N+1],table[rand()%N+1]);
}
inline void reverse(int i,int j){
	for(;i<j;i++,j--) swap(table[i],table[j]);
}
double curans(){
	double res=0;
	for(int i=1;i<N;i++) res+=dt[table[i]][table[i+1]];
	return res;
}
int main(){
	freopen("linec.in","r",stdin);
	freopen("linec.out","w",stdout);
	srand(time(NULL));
	cin>>N;
	for(int i=1;i<=N;i++) cin>>st[i].x>>st[i].y,table[i]=i;
	for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) dt[i][j]=sqrt((st[i].x-st[j].x)*(st[i].x-st[j].x)+(st[i].y-st[j].y)*(st[i].y-st[j].y));
	const int T=10000;
	for(int k=1;k<=T;k++){
		randp();
		for(int i=2;i<=N;i++) for(int j=i;j<=N-1;j++) 
			if(dt[table[i]][table[i-1]]+dt[table[j]][table[j+1]]>dt[table[i-1]][table[j]]+dt[table[i]][table[j+1]])
				 reverse(i,j);
		ans=min(curans(),ans);
	}
	cout.setf(std::ios::fixed);
	cout.precision(2);
	cout<<ans;
}