| 比赛 | 测试比赛 | 评测结果 | EEEE | 
    | 题目名称 | 加法问题 | 最终得分 | 0 | 
    | 用户昵称 | cqw | 运行时间 | 0.000 s | 
    | 代码语言 | C++ | 内存使用 | 0.00 MiB | 
    | 提交时间 | 2008-04-21 17:15:55 | 
显示代码纯文本
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int n;
FILE *fi=fopen("linec.in","r"),*fo=fopen("linec.out","w");
double dis[1000][1000];
int lt[1000];
double dist(double a1,double b1,double a2,double b2)
{
	return sqrt((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2));
}
void init()
{
	int i,j;
	double a[1000],b[1000];
	fscanf(fi,"%d",&n);
	for (i=1;i<=n;i++)
	{
		fscanf(fi,"%lf%lf",&a[i],&b[i]);
	}
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			dis[i][j]=dist(a[i],b[i],a[j],b[j]);
	
	for (i=0;i<=n;i++)
    {
        dis[0][i]=0;
        dis[i][n+1]=0;
    }
	
	for (i=1;i<=n;i++)
	{
		lt[i]=i;
	}
}
void swap(int& a,int& b)
{
	int t;
	t=a;
	a=b;
	b=t;
}
void mkhmd()
{
	int i,a,b;
	for (i=1;i<=100;i++)
	{
		a=rand()%(n-1)+1;
		b=rand()%(n-1)+1;
		swap(lt[a],lt[b]);
	}
}
void sv(int a,int b)
{
	int i,j;
	for (i=a,j=b;i<=j;i++,j--)
	{
		swap(lt[i],lt[j]);
	}
}
void change()
{
	int i,j;
	for (i=1;i<=n-1;i++)
	{
		for (j=i+1;j<=n;j++)
		{
			if (dis[ lt[i-1] ][ lt[i] ]+dis[ lt[j] ][ lt[j+1] ] > dis[ lt[i-1] ][ lt[j] ]+dis[ lt[i] ][ lt[j+1] ])
			{
				sv(i,j);
			}	
		}
	}
}
double count()
{
	int i;
	double r=0;
	for (i=1;i<=n-1;i++)
	{
		r+=dis[ lt[i] ][ lt[i+1] ];
	}
	return r;
}
int main()
{
	double c,mc=10000000;
	init();
	for (int i=1;i<=2000;i++)
	{
		mkhmd();
		change();
		c=count();
		if (c<mc)
			mc=c;
	}
	fprintf(fo,"%.2lf",mc);
	fclose(fi);
	fclose(fo);
	return 0;
}