2560.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 43 行

#include"iostream.h"
#include"math.h"
#include"stdio.h"
float x[101],y[101];
int sign[101];
typedef struct arc
{int i;
float l;
struct arc *p;
}ARC;


int main()
{int n,i,j,k,to;
double an,lest;

while(1)
{cin>>n;
if(cin.fail()||n==0)break;
for(i=0;i<n;i++){cin>>x[i]>>y[i];sign[i]=0;}

an=0;k=0;
sign[0]=1;
while(k<n-1)
{lest=999999;to=-1;
for(i=0;i<n;i++)
if(sign[i])
for(j=1;j<n;j++)if(!sign[j]&&i!=j&&(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<lest)
{lest=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);to=j;}

sign[to]=1;
an+=sqrt(lest);
k++;
}
if(an*1000-floor(an*1000)>=5)an+=0.01;

printf("%.2f\n",an);
}
return 1;
}