3270 - Simplified GSM Network

3270 - Simplified GSM Network.cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

#define N 60
#define EPS 1e-9
#define INF 1e8
#define clr(x,v) memset( x, v, sizeof(x) )

const int dcmp( const double &x ) { if( x < -EPS ) return -1; return x > EPS; }
const double ABS( const double &x ) { return (dcmp(x)<0?-x:x); }
const double sqr( const double &x ) { return x*x; }

struct Point {
	double x, y;
	Point( double _x = 0, double _y = 0 ): x(_x), y(_y) {}
	const Point operator+( const Point &op ) const { return Point( x+op.x, y+op.y ); }
	const Point operator-( const Point &op ) const { return Point( x-op.x, y-op.y ); }
	const Point operator*( const double &k ) const { return Point( x*k, y*k ); }
	const Point operator/( const double &k ) const { double t=(dcmp(k)?k:1); return Point( x/t, y/t ); }
	const double operator*( const Point &op ) const { return ( x*op.x+y*op.y ); }
	const double operator^( const Point &op ) const { return ( x*op.y-y*op.x ); }
	const bool operator==( const Point &op ) const { return ( !dcmp(x-op.x)&&!dcmp(y-op.y) ); }
	const bool operator!=( const Point &op ) const { return !((*this)==op); }
};

const double disSqr( const Point &a, const Point &b = Point() ) { return sqr(a.x-b.x)+sqr(a.y-b.y); }
const double dis( const Point &a, const Point &b = Point() ) { return sqrt(disSqr(a,b)); }

int ti = 0;
int b, c, r, q;
int edge[N][N];
int c2c[N][N];
Point bs[N], city[N];

const int findWho( const Point &p )
{
	int i, ret = 1;
	double mindis = dis( p, bs[1] );

	for( i = 2; i <= b; ++i ) if( dcmp( dis(p,bs[i])-mindis ) < 0 ) {
		ret = i;
		mindis = dis(p,bs[i]);
	}

	return ret;
}

const int getRoad( const Point &A, const Point &B )
{
	int fa = findWho(A), fb = findWho(B);

	if( fa == fb ) return 0;
	Point mid = (A+B)/2;
	if( !dcmp( dis(A,B) ) ) return 1;
	return getRoad( A, mid )+getRoad( mid, B );
}

void init( void )
{
	static int i, x, y, j;
	clr( edge, -1 );

	for( i = 1; i <= b; ++i ) scanf( "%lf%lf", &bs[i].x, &bs[i].y );
	for( i = 1; i <= c; ++i ) scanf( "%lf%lf", &city[i].x, &city[i].y );
	for( i = 1; i <= r; ++i ) {
		scanf( "%d%d", &x, &y );
		edge[x][y] = edge[y][x] = getRoad( city[x], city[y] );
	}

	for( i = 1; i <= c; ++i ) for( j = 1; j <= c; ++j ) {
		if( i == j ) c2c[i][j] = 0;
		else if( edge[i][j] >= 0 ) c2c[i][j] = edge[i][j];
		else c2c[i][j] = INF;
	}

	/*
	for( i = 1; i <= c; ++i ) {
		for( int j = 1; j <= c; ++j ) printf( "%d ", edge[i][j] );
		putchar('\n');
	}
	*/

	/*
	for( i = 1; i <= c; ++i ) {
		for( int j = 1; j <= c; ++j ) printf( "%d ", c2c[i][j] );
		putchar('\n');
	}
	*/
}

void solve( void )
{
	static int i, j, k;

	for( k = 1; k <= c; ++k ) for( i = 1; i <= c; ++i ) for( j = 1; j <= c; ++j )
		c2c[i][j] = min( c2c[i][j], c2c[i][k]+c2c[k][j] );


	/*
	for( i = 1; i <= c; ++i ) {
		for( int j = 1; j <= c; ++j ) printf( "%d ", c2c[i][j] );
		putchar('\n');
	}
	*/

}

void output( void )
{
	static int i, x, y;
	printf( "Case %d:\n", ++ti );

	for( i = 1; i <= q; ++i ) {
		scanf( "%d%d", &x, &y );
		if( c2c[x][y] == INF ) puts("Impossible");
		else printf( "%d\n", c2c[x][y] );
	}
}

int main( void )
{
	int i;

	while( scanf( "%d%d%d%d", &b, &c, &r, &q ) == 4 && (b||c||r||q) ) {
		init();
		solve();
		output();
	}

	return 0;
}