Cod sursa(job #270262)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 3 martie 2009 20:51:43
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#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;
}