比赛 |
20110318 |
评测结果 |
C |
题目名称 |
公路修建 |
最终得分 |
0 |
用户昵称 |
Citron酱 |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2011-03-18 20:52:09 |
显示代码纯文本
#include <fstream>
#include <iomanip>
#include <cmath>
#define I_F "roadz.in"
#define O_F "roadz.out"
#define MAXn 5000
#define FLOAT_MAX 3000000
using namespace std;
struct Points
{
long x,y;
};
Points p[MAXn];
float map[MAXn][MAXn];
int n;
float ans;
void Input();
float sqr(float);
void GetMap();
void Prim();
void Output();
int main()
{
Input();
GetMap();
Prim();
Output();
return 0;
}
void Input()
{
ifstream fin(I_F);
fin>>n;
for (int i=0; i<n; fin>>p[i].x>>p[i++].y);
fin.close();
}
float sqr(float x)
{
return x*x;
}
void GetMap()
{
for (int j,i=0; i<n; i++)
for (j=0; j<n; map[i][j]=sqrt(sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j++].y)));
}
void Prim()
{
bool f[MAXn]={true};
float t;
int tn;
for (int j,k,i=0; i<n-1; i++)
{
t=FLOAT_MAX;
for (j=0; j<n; j++)
if (f[j])
for (k=0; k<n; k++)
if ((!f[k])&&(map[j][k]<t))
{
t=map[j][k];
tn=k;
}
f[tn]=true;
ans+=t;
}
}
void Output()
{
ofstream fout(O_F);
fout<<setprecision(2)<<setiosflags(ios::fixed)<<ans<<'\n';
fout.close();
}