Poj Solution 3119

http://poj.org/problem?id=3119

#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 %dn", 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 fronteiran" );
            else
                printf( "Lados opostos da fronteiran" );
        }
    }
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *