Cod sursa(job #49306)

Utilizator webspiderDumitru Bogdan webspider Data 5 aprilie 2007 18:16:16
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

const int maxN = 50001;
const int maxH = 666013;

const int bazaH1 = 19;
const int bazaH2 = 23;

int n,m,w,h;
int i,j;

vector<int> tabela_dispersie[ maxH ];
int ograzi[ maxN ][ 2 ];
int ntotal;
char buff[100];
int offset;


int fdd( int a, int b )
{
	int ch = 0;
	ch = ( ch * 33 ) ^ a;
        ch = ( ch * 33 ) ^ b;
	ch = ch % maxH;
	if ( ch >= 0 )
	return ch;
	return 0;
}

int bun( int x, int y, int d )
{
	if ( d &&
	     x >= ograzi[ d ][ 0 ] && x <= ograzi[ d ][ 0 ] + h &&
	     y >= ograzi[ d ][ 1 ] && y <= ograzi[ d ][ 1 ] + w )
		return 1;
	return 0;
}

int cauta( int x, int y, int d )
{
	int i;
	if ( tabela_dispersie[ d ].size() );
	for ( i = 0; i < tabela_dispersie[ d ].size(); i++ )
		if ( bun( x, y, tabela_dispersie[ d ][ i ] ) )
		{
			ntotal++;
			return 1;
		}
	return 0;
			
}

void interior( int x, int y )
{
	int nx,ny;
	// 1
	if ( x % h ) nx = x + ( h - x % h );
	else nx = x;
	if ( y % w ) ny = y + ( w - y % w );
	else ny = y;
	if ( cauta( x, y, fdd( nx, ny ) ) ) return ;
	// 2
	if ( x % h ) nx = x + ( h - x % h );
	else nx = x;
	if ( y % w ) ny = y - ( y % w );
	else ny = y - w;
	if ( cauta( x, y, fdd( nx, ny ) ) ) return ;
	// 3
	if ( x % h ) nx = x - ( x % h );
	else nx = x - h;
	if ( y % w ) ny = y + ( w - y % w );
	else ny = y;
	if ( cauta( x, y, fdd( nx, ny ) ) ) return ;
	// 4
	if ( x % h ) nx = x - ( x % h );
	else nx = x - h;
	if ( y % w ) ny = y - ( y % w );
	else ny = y - w;
	if ( cauta( x, y, fdd( nx, ny ) ) ) return ;
}

int main()
{
	int x, y;
	int hk;
	int j;

	freopen("ograzi.in","r",stdin);
	freopen("ograzi.out","w",stdout);

	scanf("%d %d %d %d\n", &n, &m, &h, &w );

	for ( i = 1; i <= n; i++ )
	{
		gets(buff);
		x = y = 0;
		for ( j = 0; buff[j] != ' '; j++ ) x = ( x * 10 ) + buff[j] - '0' ;
		for ( j = j+1; buff[j] != '\0'; j++ ) y = ( y * 10 ) + buff[j] - '0';

		ograzi[ i ][ 0 ] = x;
		ograzi[ i ][ 1 ] = y;

		// Sa determinam carui punct asociem dreptunghiul
		
		if ( x % h != 0 ) x += h - ( x%h );
		if ( y % w != 0 ) y += w - ( y%w );

		hk = fdd( x, y );
		if ( hk >= 0 )
		tabela_dispersie[ hk ].push_back( i );
	}

	for ( i = 1; i <= m; i++ )
	{
		gets(buff);
		x = y = 0;
		for ( j = 0; buff[j] != ' '; j++ ) x = ( x * 10 ) + buff[j] - '0' ;
		for ( j = j+1; buff[j] != '\0'; j++ ) y = ( y * 10 ) + buff[j] - '0';

		interior(x,y);
	}

	printf("%d\n", ntotal );

	fclose(stdin);
	fclose(stdout);

	return 0;
}