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