3119.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3119  User Id:fzk 
Memory:552K  Time:328MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int sx[65536], sy[65536];
int c, r, to;
const int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };

void next( int &x, int &y ) {
	c++;
	if( c == (2*r-1)*(2*r-1) ) {
		to = 0;
		r++;
		x--;
		return;
	}

	x += dx[to];
	y += dy[to];

	if( abs(x) == r-1 && abs(y) == r-1 )
		to = (to+1)%4;
}

int main( ) {
	int n, i, a, b, caso, k, x, y, s1, s2;

	scanf( "%d", &caso );

	for( k=1; k<=caso; k++ ){

		scanf( "%d%d", &a, &b );
		c = 0; r = 1; to = 0;

		x = y = 0;

		for( i=0; i<65536; i++ ) {
			while( x*a+b == y )
				next( x, y );
			sx[i] = x;
			sy[i] = y;
			next( x, y );
		}

		scanf( "%d", &n );
		printf( "Caso %d\n", k );

		while( n-- ) {
			scanf( "%d%d", &s1, &s2 );
			if( (sx[s1]*a+b<sy[s1]) == (sx[s2]*a+b<sy[s2]) )
				printf( "Mesmo lado da fronteira\n" );
			else
				printf( "Lados opostos da fronteira\n" );
		}
	}
	return 0;
}