Cod sursa(job #48692)

Utilizator webspiderDumitru Bogdan webspider Data 4 aprilie 2007 23:53:07
Problema Ograzi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.75 kb
#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

const int maxN = 50001;
const int maxH = 2999999;

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*bazaH2 + b ) % maxH;
	return cheie;
}

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;
}




void coincide_total( int x, int y )
{
	int d;
	int nx, ny;
	vector<int>::iterator it;

	// Primul
	
	d = tabela_dispersie[ fdd( x, y ) ].size();

	if ( d )
	for ( it = tabela_dispersie[ fdd( x, y ) ].begin(); it != tabela_dispersie[ fdd( x, y ) ].end(); it++ )
	if ( bun( x, y, *it ) ) {
		ntotal++;
		return ;
	}


	// Al doilea
	
	nx = x;
	ny = y - w;
	if ( nx >= 0 && ny >= 0 ) {

	d = tabela_dispersie[ fdd( nx , ny ) ].size();
	if ( d )
	for ( it = tabela_dispersie[ fdd( nx,ny ) ].begin(); it != tabela_dispersie[ fdd( nx, ny ) ].end(); it ++ )
	if ( bun( x, y, *it ) )
	{
		ntotal++;
		return;
	}

        }


	// Al treilea
	
	nx = x - h;
	ny = y;
	
	if ( nx >= 0 && ny >= 0 ) {
	

	d = tabela_dispersie[ fdd( nx, ny ) ].size();

	if( d )
	for ( it = tabela_dispersie[ fdd( nx, ny ) ].begin(); it != tabela_dispersie[ fdd( nx, ny ) ].end(); it++ )
	if ( bun( x, y, *it ) )
	{
		ntotal++;
		return ;
	}

	}

	// Al patrulea 
	
	nx = x - h;
	ny = y - w;
	
	if ( nx >= 0 && ny >= 0 ) {

	d = tabela_dispersie[ fdd( nx, ny ) ].size();
	if ( d )
	for ( it = tabela_dispersie[ fdd( nx, ny ) ].begin(); it != tabela_dispersie[ fdd( nx, ny ) ].end(); it++ )
	if ( bun( x, y, *it ) )
	{
		ntotal++;
		return ;
	}

	}
}


void interior( int x, int y )
{
	int d;
	int nx, ny;
	vector<int>::iterator it;

	// Primul
	
	nx = x + ( h - x % h );
	ny = y + ( w - y % w );

	if ( nx >= 0 && ny >= 0 )
	{

	d = tabela_dispersie[ fdd( nx, ny ) ].size();
	if ( d )
	for ( it = tabela_dispersie[ fdd( nx, ny ) ].begin(); it != tabela_dispersie[ fdd( nx, ny ) ].end(); it++ )
	if ( bun( x, y, *it ) ) {
		ntotal++;
		return ;
	}

	}
	

	// Al doilea
	
	nx = x + ( h - x % h );
	ny = y - ( y % w );

	if ( nx >= 0 && ny >= 0 ) {

	d = tabela_dispersie[ fdd( nx , ny ) ].size();
	if ( d )
	for ( it = tabela_dispersie[ fdd( nx, ny ) ].begin(); it != tabela_dispersie[ fdd( nx, ny ) ].end(); it++ )
	if ( bun( x, y, *it ) )
	{
		ntotal++;
		return;
	}
        
	}

	// Al treilea
	
	nx = x - ( x % h );
	ny = y + ( w - y % w );
	
	if ( nx >= 0 && ny >= 0 ) {

	d = tabela_dispersie[ fdd( nx, ny ) ].size();
	if ( d )
	for ( it = tabela_dispersie[ fdd( nx, ny ) ].begin(); it != tabela_dispersie[ fdd( nx, ny ) ].end(); it ++ )
	if ( bun( x, y, *it ) )
	{
		ntotal++;
		return ;
	}

	}

	// Al patrulea 
	
	nx = x - ( x % h );
	ny = y - ( y % w );
	
	if ( nx >= 0 && ny >= 0 ) {

	d = tabela_dispersie[ fdd( nx, ny ) ].size();
	if ( d )
	for ( it = tabela_dispersie[ fdd( nx, ny ) ].begin(); it != tabela_dispersie[ fdd( nx, ny ) ].end(); it++ )
	if ( bun( x, y, *it ) )
	{
		ntotal++;
		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 );
		
		tabela_dispersie[ hk ].push_back( i );
	}

	for ( i = 1; i <= m; i++ )
	{
		scanf("%d %d\n", &x, &y );

		if ( x % h == 0 && y % w == 0 )
			coincide_total(x,y);
		else
			interior(x,y);
	}

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

	fclose(stdin);
	fclose(stdout);

	return 0;
}