UVa 10034 - Freckles

//aarifshuvo  ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

typedef pair<double,double> pii;

struct edge
{
    int a,b;
    double c;

    edge(int _a, int _b, double _c)
    {
        a=_a, b=_b, c=_c;
    }

    bool operator < (const edge p) const
    {
        return c < p.c;
    }
};

double dist(double x1, double y1, double x2, double y2)
{
    double d = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
    return d;
}

vector <pii> points;
vector<edge> edges;
map<int,int> par;

int findr(int r)
{
    if(par[r]==0) return r;

    int x = findr(par[r]);
    par[r] = x;
    return x;
}

int main()
{
    bool fl = false;
    int t,n;
    double x,y;
    scanf("%d", &t);
    getchar();
    while(t--)
    {
        if(fl) printf("\n"); fl = true;

        points.clear();
        edges.clear();
        par.clear();

        scanf("%d", &n);

        REP(i,n)
        {
             scanf("%lf%lf", &x, &y);
             points.push_back(make_pair(x,y));
        }

        REP(i,n)
        {
            FOR(j,i+1,n-1)
            {

                int ii = i+1, jj = j+1;
                double dd = dist(points[i].first, points[i].second,
                                points[j].first, points[j].second);

                edges.push_back(edge(ii,jj,dd));
            }
        }

        sort(ALL(edges));

        double mstsm = 0;

        REP(i,SZ(edges))
        {
            int u = findr(edges[i].a),
                v = findr(edges[i].b);

            if(u!=v) par[v] = u, mstsm += edges[i].c;
        }

        printf("%.2lf\n", mstsm);

    }
    return 0;
}