比赛 测试比赛 评测结果 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;
}