Pagini recente » Cod sursa (job #820004) | Cod sursa (job #942035) | Cod sursa (job #2946712) | Cod sursa (job #895085) | Cod sursa (job #2042125)
#include <iostream>
#include <fstream>
#include <cmath>
#define N_MAX 3005
#define inf (1 << 31) -1
#include <iomanip>
using namespace std;
ifstream f("cablaj.in");
ofstream g("cablaj.out");
struct punct
{
int x;
int y;
};
int n;
bool inApm[N_MAX];
double dist[N_MAX];
punct p[N_MAX];
double dist2Pct(punct p1, punct p2)
{
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
void prim()
{
int ok = 1, nod = 1;
for(int i = 1; i <= n; i++)
dist[i] = inf;
dist[1] = 0;
inApm[1] = 1;
double minn;
while(ok)
{
ok = 0;
minn = inf;
for(int i = 1; i <= n; i++)
{
if(!inApm[i])
{
ok = 1;
dist[i] = min(dist[i], dist2Pct(p[nod], p[i]));
if(minn > dist[i])
{
minn = dist[i];
nod = i;
}
}
}
inApm[nod] = 1;
}
}
int main()
{
f >> n;
for(int i = 1; i <= n; i++)
{
f >> p[i].x >> p[i].y;
}
prim();
double s = 0;
for(int i = 1; i <= n; i++)
s += dist[i];
g << fixed << setprecision(4) << s << "\n";
return 0;
}