# HackerEarth Make Paths problem solution

In this HackerEarth Make Paths problem solution Walter White and Jesse Pinkman have now established their bases at different places.
Now they want to form a network, that is, they want that all their bases should be reachable from every base.
One base is reachable from another base if there is a path of tunnels connecting bases.
Bases are supposed based on a 2-D plane having integer coordinates.
Cost of building tunnels between two bases are coordinates (x1,y1) and (x2,y2) is min{ |x1-x2|, |y1-y2| }.

What is the minimum cost such that a network is formed.

## HackerEarth Make Paths problem solution.

`#include <algorithm>#include <functional>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <vector>#include <string>using namespace std;const int MAXN = 100100;int n;struct planet {    int x, y;    int indeks;    friend bool operator < ( const planet &A, const planet &B ) {        if( A.x != B.x ) return A.x < B.x;        if( A.y != B.y ) return A.y < B.y;        return false;    }    friend int dist( const planet &A, const planet &B ) {         return min( abs( A.x-B.x ), abs( A.y-B.y ) );    }} P[ MAXN ], Org[ MAXN ]; struct edge {    int ind_a, ind_b;    int cost;        edge( int _a, int _b ) : ind_a( _a ), ind_b( _b ) {        cost = dist( Org[ind_a], Org[ind_b] );    }    friend bool operator < ( const edge &A, const edge &B ) {        return A.cost < B.cost;    }};vector< edge > E; // 3.5 MBbool x_cmpf( const planet &A, const planet &B ) { return A.x < B.x; }bool y_cmpf( const planet &A, const planet &B ) { return A.y < B.y; }int dad[ MAXN ];int find_dad( int x ) {    if( dad[x] == -1 ) return x;    return dad[x] = find_dad( dad[x] );}int main( void ){    int temp;    scanf( "%d", &n );    E.reserve( 3*n + 100 );    for( int i = 0; i < n; ++i ) {//        scanf( "%d %d %d", &P[i].x, &P[i].y, &P[i].z );        scanf( "%d %d", &P[i].x, &P[i].y);        P[i].indeks = i;        Org[i] = P[i];    }    sort( P, P+n );    for( int i = 1; i < n; ++i )        if( !( P[i] < P[i-1] || P[i-1] < P[i] ) ) {                puts( "GRESKA TESKA -> jednake vrijednosti!" );                exit( 1 );            }    sort( P, P+n, x_cmpf );    for( int i = 1; i < n; ++i )        E.push_back( edge( P[i-1].indeks, P[i].indeks ) );    sort( P, P+n, y_cmpf );    for( int i = 1; i < n; ++i )        E.push_back( edge( P[i-1].indeks, P[i].indeks ) );    sort( E.begin(), E.end() );    long long sum = 0;    memset( dad, -1, sizeof dad );    for( vector< edge >::iterator it = E.begin(); it != E.end(); ++it ) {        int A = find_dad( it->ind_a );        int B = find_dad( it->ind_b );        if( A != B ) {            sum += it->cost;            dad[A] = B;        }    }    printf( "%lld\n", sum );    return (0-0);}`

### Second solution

`#include <cstdio>#include <vector>#include <algorithm>#include <queue>#include <cstdlib>using namespace std;#define MAX 100010//vector<pair<int, long long> > Graph[MAX];vector<pair<int, int> > X;vector<pair<int, int> > Y;//vector<pair<int, pair<int, int> > > nodes;int N;priority_queue<pair<long long, pair<int, int> > > Q;int parent[MAX];int size[MAX];int getP(int n){    while(n!=parent[n])        n = parent[n];    return n;}bool combine(int n1, int n2){    int p1 = getP(n1);    int p2 = getP(n2);    if(p1==p2)        return false;    if(size[p1]<size[p2]){        size[p2] += size[p1];        parent[p1] = p2;    }else{        size[p1] += size[p2];        parent[p2] = p1;    }    return true;}int main(){    int x, y;    scanf("%d", &N);    for(int i=0;i<N;i++){        scanf("%d %d", &x, &y);        X.push_back(make_pair(x, i));        Y.push_back(make_pair(y, i));    }    sort(X.begin(), X.begin()+N);    sort(Y.begin(), Y.begin()+N);    pair<int, int> a, b;    for(int i=0;i<N-1;i++){        a = X[i];        b = X[i+1];        Q.push(make_pair(-abs(b.first-a.first), make_pair(a.second, b.second)));    }    for(int i=0;i<N-1;i++){        a = Y[i];        b = Y[i+1];        Q.push(make_pair(-abs(b.first-a.first), make_pair(a.second, b.second)));    }    for(int i=0;i<N;i++){        parent[i]=i;        size[i]=1;    }    long long ans = 0;    int node1, node2;    while(!Q.empty()){        pair<long long, pair<int, int> > p = Q.top(); Q.pop();        node1 = p.second.first;        node2 = p.second.second;        if(combine(node1, node2)){            ans = ans - p.first;        }    }    printf("%lld\n", ans);}`