Pagini recente » Cod sursa (job #2800838) | Cod sursa (job #2072825) | Cod sursa (job #1508420) | Cod sursa (job #743444) | Cod sursa (job #270262)
Cod sursa(job #270262)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int N, t[1005], root;
struct muchie
{
int x, y, c;
} v[100004];
struct punct
{
int x, y;
} a[1005];
vector <muchie> apm, muc;
int cmp (struct muchie x, struct muchie y)
{
return x.c < y.c;
}
double dist(punct x, punct y)
{
return (x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y);
}
int min(int x, int y) { return x < y ? x : y;}
int find_root(int x)
{
while (t[x] != x) x = t[x];
return x;
}
int main()
{
freopen("desen.in","r",stdin);
freopen("desen.out","w",stdout);
int i, j, n;
muchie nou;
scanf("%d",&N);
for (i = 1; i <= N; i++) scanf("%d %d", &a[i].x, &a[i].y);
for (i = 1; i <= N; i++)
{
muc.clear();
muc = apm;
apm.clear();
double cost = 0;
for (j = 1; j < i; j++)
{
nou.x = i; nou.y = j;
nou.c = dist(a[i], a[j]);
muc.push_back(nou);
}
sort(muc.begin(), muc.end(), cmp);
n = muc.size();
for (j = 1; j <= i; j++) t[j] = j;
for (j = 0; j < n; j++)
{
int x, y;
x = find_root(muc[j].x);
y = find_root(muc[j].y);
if (x != y)
{
apm.push_back(muc[j]);
t[x] = y;
cost += sqrt(muc[j].c);
}
}
printf("%.6lf\n",cost);
}
return 0;
}