记录编号	30701	评测结果	AAAAWAAAAA
题目名称	线型网络	最终得分	90
用户昵称	201101	是否通过	未通过
代码语言	C++	运行时间	4.633 s
提交时间	2011-10-30 21:25:59	内存使用	0.26 MiB

#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;

int n;
double x[20],y[20],minnum=1000000;

void swapint(int& a,int& b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

void swapdouble(double& a,double& b)
{
	double temp;
	temp=a;
	a=b;
	b=temp;
}

void swapalldouble(int l,int r)
{
	int i,j;
	for (i=l,j=r;i<j;i++,j--)
	{
		swapdouble(x[i],x[j]);
		swapdouble(y[i],y[j]);
	}
}

void makelist(void)
{
	int i,temp,temp2;
	for (i=0;i<5;i++)
	{
		temp=rand()%n;
		temp2=rand()%n;
		swapdouble(x[temp],x[temp2]);
		swapdouble(y[temp],y[temp2]);
	}
}

void checklist(void)
{
	int i,j;
	if ((x[0]-x[2])*(x[0]-x[2])+(y[0]-y[2])*(y[0]-y[2])<(x[0]-x[1])*(x[0]-x[1])+(y[0]-y[1])*(y[0]-y[1]))
	{
		swapdouble(x[1],x[2]);
		swapdouble(y[1],y[2]);
	}
	if ((x[n-1]-x[n-3])*(x[n-1]-x[n-3])+(y[n-1]-y[n-3])*(y[n-1]-y[n-3])<(x[n-1]-x[n-2])*(x[n-1]-x[n-2])+(y[n-1]-y[n-2])*(y[n-1]-y[n-2]))
	{
		swapdouble(x[1],x[2]);
		swapdouble(y[1],y[2]);
	}
	for (i=0;i<n-1;i++)
		for (j=i+1;j<n;j++)
		{
			if ((x[i]-x[i+1]) * (x[i]-x[i+1]) + (y[i]-y[i+1]) * (y[i]-y[i+1]) +
				(x[j]-x[j-1]) * (x[j]-x[j-1]) + (y[j]-y[j-1]) * (y[j]-y[j-1]) >
				(x[i]-x[j-1]) * (x[i]-x[j-1]) + (y[i]-y[j-1]) * (y[i]-y[j-1]) +
				(x[j]-x[i+1]) * (x[j]-x[i+1]) + (y[j]-y[i+1]) * (y[j]-y[i+1]) )
				swapalldouble(i+1,j-1);
		}
}

void getvalue(void)
{
	int i;
	double temp=0;
	for (i=0;i<n-1;i++)
	{
		temp+=sqrt( (x[i]-x[i+1]) * (x[i]-x[i+1] ) + (y[i]-y[i+1]) * (y[i]-y[i+1]) );
		if (temp>=minnum)
			return;
	}
	minnum=temp;
}

int main(void)
{
	srand(676);
	freopen("linec.in","r",stdin);
	freopen("linec.out","w",stdout);
	int i;
	scanf("%d\n",&n);
	for (i=0;i<n;i++)
		scanf("%lf %lf\n",&x[i],&y[i]);
	for (i=0;i<150000;i++)
	{
		checklist();
		getvalue();
		makelist();
	}
	checklist();
	getvalue();
	printf("%.2lf\n",minnum);
	fclose(stdin);
	fclose(stdout);
	return(0);
}