10397 - Connect the Campus

10397 - Connect the Campus.cpp

/**
 * Tittle:	10397 - Connect the Campus
 * Author:	Cheng-Shih, Wong
 * Date:	2015/08/13
 */

// include files
#include <bits/stdc++.h>

using namespace std;

// definitions
#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
#define clr(x,v) memset( x, v, sizeof(x) )
#define F first
#define S second
#define PB push_back
#define N 1000

class Point {
public:
	double x, y;

	Point( double _x=0, double _y=0 ):
		x(_x), y(_y) {}

	Point &read() {
		cin >> x >> y;
		return *this;
	}

	double dis( const Point &op ) const {
		return sqrt( (x-op.x)*(x-op.x)+(y-op.y)*(y-op.y) );
	}
};

class Edge {
public:
	int u, v;
	double dis;

	Edge( int _u=0, int _v=0, double _d=0 ):
		u(_u), v(_v), dis(_d) {}

	const bool operator<( const Edge &op ) const {
		return dis < op.dis;
	}
};

typedef vector<Point> VP;
typedef vector<Edge> VE;

// declarations
int n, m;
VP buildings;
VE connections;

// functions
int fat[N];
int findSet( int p )
{
	if( fat[p] < 0 ) return p;
	return (fat[p] = findSet(fat[p]));
}

void unionSet( int p, int q )
{
	p = findSet( p );
	q = findSet( q );

	if( p!=q )
		fat[p] = q;
}

void init()
{
	static int u, v;

	buildings.clear();
	buildings.PB( Point() );

	FOR( i, 1, n )
		buildings.PB( Point().read() );

	cin >> m;
	clr( fat, -1 );

	while( m-- ) {
		cin >> u >> v;
		unionSet( u, v );
	}

	connections.clear();
	FOR( i, 1, n ) FOR( j, i+1, n ) {
		connections.PB( Edge(i, j, buildings[i].dis( buildings[j] )) );
	}
	
}

void solve()
{
	double ans = 0.0;
	
	sort( connections.begin(), connections.end() );

	for( Edge e : connections ) {
		if( findSet(e.u) != findSet(e.v) ) {
			ans += e.dis;
			unionSet(e.u,e.v);
		}
	}

	// output
	printf( "%.2lf\n", ans );
}

// main function
int main( void )
{

	// input
	while( cin >> n ) {
		init();
		solve();
	}
	
	return 0;
}