比赛 |
HAOI2009 模拟试题3 |
评测结果 |
AAAAAAAAAA |
题目名称 |
公路修建 |
最终得分 |
100 |
用户昵称 |
TBK |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2012-06-28 14:20:01 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <iomanip>
#define MMM 1000000
#define MAXN 0x7fffffff
using namespace std;
int b,c,d,l,n[5000],r[5000][2]={0};
double s=0,k,m[5000];
bool bo[5000]={false};
double ab(double z)
{
return z>0?z:-z;
}
double jisuan(int x,int y)
{
double p,q;
p=fabs((double)(r[x][1]-r[y][1]))*fabs((double)(r[x][1]-r[y][1]));
q=fabs((double)(r[x][0]-r[y][0]))*fabs((double)(r[x][0]-r[y][0]));
return sqrt(p+q);
}
int main(void)
{
freopen ("roadz.in","r",stdin);
freopen ("roadz.out","w",stdout);
scanf("%d",&b);
for (c=0;c<b;c++)
{
scanf("%d%d",&r[c][0],&r[c][1]);
r[c][0]+=MMM;
r[c][1]+=MMM;
}
bo[0]=true;
for(c=1;c<b;c++)
{
m[c]=jisuan(0,c);
n[c]=0;
}
for (c=1;c<b;c++)
{
k=MAXN;
l=0;
for (d=0;d<b;d++)
if ((bo[d]==false)&&(m[d]<k))
{
k=m[d];
l=d;
}
s+=m[l];
bo[l]=true;
for (d=0;d<b;d++)
if ((bo[d]==false)&&(jisuan(d,l)<m[d]))
{
m[d]=jisuan(d,l);
n[d]=l;
}
}
printf("%.2lf",s);
fclose(stdin);
fclose(stdout);
return 0;
}