11228 - Transportation system

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

struct Edge{ int a, b, d; } edge[500000];

bool cmp(const Edge &a, const Edge &b)
{
    return a.d<b.d;
}
int parent(int p, int *root)
{
    return p==root[p]?p:root[p]=parent(root[p], root);
}
int main()
{
    int cases;
    scanf("%d", &cases);

    for(int n, r, cnt=1; cnt<=cases && scanf("%d%d", &n, &r); cnt++)
    {
        double road=0, rail=0;
        int state=n, num=0, x[n], y[n], root[n];

        for(int i=0; i<n; i++)
            scanf("%d%d", x+i, y+i), root[i]=i;

        for(int i=1; i<n; i++)
            for(int j=0; j<i; j++)
                edge[num++]={i, j, (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])};

        sort(edge, edge+num, cmp);

        for(int i=0, t=1; i<num && t<n; i++)
        {
            int a=parent(edge[i].a, root), b=parent(edge[i].b, root);

            if(a!=b)
            {
                root[a]=b, ++t;

                if(edge[i].d<=r*r)
                    road+=sqrt(edge[i].d), --state;
                else
                    rail+=sqrt(edge[i].d);
            }
        }
        printf("Case #%d: %d %.lf %.lf\n", cnt, state, road, rail);
    }
}