10034 - Freckles

#include <cstdio>
#include <vector>
#include<cmath>
#include <algorithm>
#define EDGE pair<int,int >
#define MAX 105
using namespace std;

vector < pair < double,EDGE > > GRAPH;
int parent[MAX];
int findset(int x, int *parent);
double Kruskal(int);

int main()
{
    int t,i,j,n;
    double x[MAX],y[MAX],z;
    freopen("in.txt","r",stdin);

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        GRAPH.clear();

        for(i=0;i<n;i++)
            scanf("%lf%lf",&x[i],&y[i]);

        for(i=0;i<n;i++)
            for(j=i+1;j<n;j++)
            {
                z = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                GRAPH.push_back(pair< double, EDGE >(z, EDGE(i, j)));
            }
        for(i=0;i<n;i++)
            parent[i] = i;

        n = n*(n-1)/2;

        z = Kruskal(n);
        printf("%0.2lf\n",z);

        if(t)
            printf("\n");
    }
    return 0;
}

int findset(int x, int *parent)
{
    if(x != parent[x])
        parent[x] = findset(parent[x], parent);
    return parent[x];
}

double Kruskal(int e)
{
    int i,pu,pv;
    double total=0;
    sort(GRAPH.begin(), GRAPH.end()); // increasing weight
    for(i=0; i<e; i++)
    {
        pu = findset(GRAPH[i].second.first, parent);
        pv = findset(GRAPH[i].second.second, parent);
        if(pu != pv)
        {
            total += GRAPH[i].first; // add edge cost
            parent[pu] = parent[pv]; // link
        }
    }
    return total;
}