Pagini recente » Cod sursa (job #1886531) | Cod sursa (job #2055939) | Cod sursa (job #1082879) | Cod sursa (job #2887263) | Cod sursa (job #965585)
Cod sursa(job #965585)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
#define N 105
#define aa second.first
#define bb second.second
ifstream fin("desen.in");
ofstream fout("desen.out");
int n, m, t[N];
double sol;
typedef pair <int, int> muchie;
typedef pair <double, muchie> arbore;
vector <arbore> graf;
vector <muchie> nod;
vector <bool> rez;
double cost(int x, int y, int a, int b)
{
double dx = a-x, dy = b - y;
return sqrt(dx*dx + dy*dy);
}
int tata(int x)
{
if(t[x] != x) t[x] = tata(t[x]);
return t[x];
}
void apm(int nn)
{
for(int i=0; rez.size() < nn-1 && i < m; i++)
{
int x = tata(graf[i].aa), y = tata(graf[i].bb);
if(x != y)
{
t[x] = y;
sol += graf[i].first;
rez.push_back(1);
}
}
}
int main()
{
fin>>n;
nod.push_back(muchie(0, 0));
for(int i=1; i<=n; i++)
{
int x, y;
fin>>x>>y;
nod.push_back(muchie(x, y));
for(int j=1; j<nod.size()-1; j++)
{
double c = cost(x, y, nod[j].first, nod[j].second);
graf.push_back(arbore(c, muchie(j, i)));
}
for(int k=1; k<=i; k++) t[k] = k;
sol = 0;
sort(graf.begin(), graf.end());
rez.clear(); m = graf.size();
apm(i);
fout<<fixed<<sol<<setprecision(6)<<'\n';
}
return 0;
}