Pagini recente » Cod sursa (job #956601) | Cod sursa (job #1078680) | Cod sursa (job #3219877) | Cod sursa (job #1349162) | Cod sursa (job #2644427)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("desen.in");
ofstream g("desen.out");
vector <int> Node[1001];
int n, index, l, T[1001], R[1001];
struct Edge
{
int x, y;
double distance;
}E[499501]; //possible number of edges
bool method(Edge a, Edge b)
{
return a.distance < b.distance; //or'='
}
int find(int x)
{
if (T[x] == x)return x;
else return T[x] = find(T[x]);
}
void Union(int x, int y)
{
if (R[x] > R[y]) T[y] = x;
if (R[y] > R[x])T[x] = y;
if (R[x] == R[y])
{
T[x] = y;
R[y]++;
}
}
void read()
{
f >> n;
for (int i = 1; i <= n; i++)
{
int x, y;
f >> x >> y;
Node[i].push_back(x);
Node[i].push_back(y);
double S = 0;
for (int j = 1; j <= i; j++)
{
T[j] = j; R[j] = 1;
}
for (int j = 1; j <= i; j++) {
E[++index].distance = sqrt(pow(Node[i][0] - Node[j][0], 2) + pow(Node[i][1] - Node[j][1], 2));
E[index].x = i; E[index].y = j;
}
sort(E + 1, E + index + 1, method);
for (int j = 1; j <= index; j++)
{
int fx = find(E[j].x), fy = find(E[j].y);
if (fx != fy)
{
Union(fx, fy);
S += E[j].distance;
}
}
g << fixed << setprecision(8) << S << '\n';
}
}
int main()
{
read();
}