Cod sursa(job #49290)

Utilizator webspiderDumitru Bogdan webspider Data 5 aprilie 2007 18:00:19
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 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;


int fdd( int a, int b )
{
	int cheie = ( a*bazaH1 + b*bazaH2 ) % maxH;
	if ( cheie >= 0 )
	return cheie;
	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;

	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++ )
	{
		scanf("%d %d\n", &x, &y );

		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++ )
	{
		scanf("%d %d\n", &x, &y );
		interior(x,y);
	}

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

	fclose(stdin);
	fclose(stdout);

	return 0;
}