UVa 10034 - Freckles

#include<bits/stdc++.h>
#define mx 100009
using namespace std;
typedef long long ll;
struct edge
{
    int u,v;
    double w;
    bool operator < (const edge& p) const
    {
        return w<p.w;
    }
};
int pr[mx];
vector<edge>e;
int fnd(int r)
{
    return (pr[r]==r)?r:fnd(pr[r]);
}
double mst(int n)
{
    sort(e.begin(),e.end());
    for(int i=1;i<=n;i++)
    {
        pr[i]=i;
    }
    int cnt=0;
    double s=0.0;
    for(int i=0;i<(int)e.size();i++)
    {
        int u=fnd(e[i].u);
        int v=fnd(e[i].v);
        if(u!=v)
        {
            pr[u]=v;
            cnt++;
            s+=e[i].w;
            if(cnt==n-1)
                break;
        }
    }
    return s;
}
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {

        cin>>n;
        vector< pair<double,double> >v;
        v.clear();
        e.clear();
        for(i=1;i<=n;i++)
        {
            double x,y;
            cin>>x>>y;
            v.push_back(make_pair(x,y));
        }
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                double x1,x2,y1,y2;
                double d=sqrt((v[i].first-v[j].first)*(v[i].first-v[j].first)+(v[i].second-v[j].second)*(v[i].second-v[j].second));
                double u,v;
                edge get;
                get.u=i+1;
                get.v=j+1;
                get.w=d;
                e.push_back(get);
            }
        }
        printf("%.2f\n",mst(n));
        if(k<test)
            printf("\n");
    }
    return 0;
}