uva_11228.cpp

#include<bits/stdc++.h>

using namespace std ;

#define M 1000000
#define pii pair<int , int >
#define mp make_pair
#define pf printf
#define sf scanf
#define sf1(a ) scanf("%d",&a)
#define pb push_back
#define sf2(a, b) scanf("%d%d",&a ,&b)
#define rep(i,n) for(i = 0 ; i< n ;i++ )

struct nd
{
    int x, y ;

};

struct ed
{
    int p,q ;
    double dis ;

};

int num, arr[M];

bool comp(ed p, ed q )
{
    return p.dis < q.dis;

}

vector<ed > edges;
vector<nd> node ;

int find(int a)
{
    if(arr[a ] == a ) return a ;
    else
        return arr[a ] =  find(arr[a]);
}

void make(int a, int b )
{
    int u =  find(a );
    int v =  find(b );
    if(u != v )arr[u] =  arr[v];



}
double states,roads, rails ;
void mst(int hold )
{
    int i, j,k ;
    rep(i, num ) arr[i] =  i ;
    double rd, rl ;
    rd = rl =  0 ;
    int count =  0;

    for( i  = 0 ; i < edges.size() ; i++)
    {
        if(find(edges[i].p ) != find(edges[i].q) )
        {
            //       pf("herr %d %d %lf\n",edges[i].p , edges[i].q ,edges[i].dis );
            if(edges[i].dis > hold )
            {

                count++;
                rl+= edges[i].dis ;
            }
            else
            {
                rd+= edges[i].dis ;
            }
            make(edges[i].p,edges[i].q);
        }
    }

    roads =   rd;
    rails =  rl ;
    states = count + 1 ;

}
int _round(double d)
{
    if (d < 0)
    {
        return (int)(d - 0.5);
    }
    return (int)(d + 0.5);
}

int main()
{

    // freopen("in.txt","r" , stdin );
    // freopen("out.txt","w" , stdout );

    int i, j,k,tc, cs = 0 ;
    sf1(tc );
    int nodes, hold ;
    while(scanf("%d%d",&nodes,&hold )==2)
    {
        node.clear();
        edges.clear();
        num =  nodes ;
        while(nodes--)
        {
            nd  var;
            int a, b ;
            sf2(a, b);
            var.x  = a;
            var.y  = b;
            node.pb(var );

        }
        for(i = 0 ; i< node.size()-1 ; i++)
        {
            for(j =  i+1 ; j< node.size(); j++)
            {
                nd var ;
                int a, b,c,d;
                a =  node[i].x ;
                b =  node[i].y ;

                c =  node[j].x ;
                d =  node[j].y  ;

                double dist ;
                dist = (double )sqrt((a-c)*(a-c) + (b-d)*(b-d) );
                //pf("%d %d %d %d dist %lf\n",a, b ,c ,d, dist);
                ed k_var ;
                k_var.dis = dist ;
                k_var.p = i ;
                k_var.q = j ;
                edges.pb(k_var );





            }

        }


        sort(edges.begin(), edges.end(), comp);
        // for(i = 0 ;i< edges.size() ; i++)
        //   pf("%lf\n",edges[i].dis );
        mst(hold);

        pf("Case #%d: %d %d %d\n",++cs, _round(states),
           _round(roads),
           _round(rails));

    }
    return 0 ;
}