Cod sursa(job #49257)

Utilizator webspiderDumitru Bogdan webspider Data 5 aprilie 2007 17:21:42
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 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*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 cauta( int x, int y, int d )
{
	int i;
	for ( i = 0; i < tabela_dispersie[ d ].size(); i++ )
		if ( bun( x, y, tabela_dispersie[ d ][ i ] ) )
			ntotal++;
}

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

void coincide_total( int x, int y )
{
	int nx,ny;
	// 1
	nx = x;
	ny = y;
	cauta( x, y, fdd( nx, ny ) );
	// 2
	nx = x - h;
	ny = y;
	cauta( x, y, fdd( nx, ny ) );
	// 3
	nx = x;
	ny = y - w;
	cauta( x, y, fdd( nx, ny ) );
	// 4
	nx = x - h;
	ny = y - w;
	cauta( x, y, fdd( nx, ny ) );
}
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;
}