Cod sursa(job #877369)

Utilizator veleanduAlex Velea veleandu Data 12 februarie 2013 20:11:39
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>

#include <vector>
using namespace std;

#define MOD 666013
#define max_n 50005

struct point {
	int x,y;
} Rectangle[ max_n ], sheep;

vector<int> Hash[ MOD ];

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

int get_value ( int x, int y ){
	int rez=0;
	rez = x / w;
	rez = ( 1LL*rez*ww ) % MOD;
	rez += y/h;
	if ( rez > MOD )
		rez -= MOD;
	return rez;
}

int main(){

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

	scanf ("%d %d %d %d", &n, &m, &w, &h );
	ww = 1000000 / w;
	ww++;
	for ( i=1; i<=n; ++i ){
		scanf ("%d %d", &Rectangle[ i ].x, &Rectangle[ i ].y );
		int nr;
		nr = get_value ( Rectangle[ i ].x, Rectangle[ i ].y );
 		Hash[ nr ].push_back( i );
 		
		nr = get_value ( Rectangle[ i ].x + w, Rectangle[ i ].y + h);
 		Hash[ nr ].push_back( i );
		
		nr = get_value ( Rectangle[ i ].x + w, Rectangle[ i ].y );
 		Hash[ nr ].push_back( i );
		
		nr = get_value ( Rectangle[ i ].x, Rectangle[ i ].y + h);
 		Hash[ nr ].push_back( i );
		//printf("%d @ \n",nr);
	}
	int rez=0;
	for ( ; m; --m ){
		scanf ("%d %d", &sheep.x, &sheep.y );
		int nr = get_value( sheep.x, sheep.y );
//		printf("%d @ \n",nr);
 		bool ok=0;
        for ( i=0; i< Hash[ nr ].size() && !ok; ++i ){
 			if ( sheep.x >= Rectangle[ Hash[ nr ][ i ] ].x &&
				sheep.x <= Rectangle[ Hash[ nr ][ i ] ].x + w &&
				sheep.y >= Rectangle[ Hash[ nr ][ i ] ].y &&
				sheep.y <= Rectangle[ Hash[ nr ][ i ] ].y + h )
				ok=1;
		}
		rez+=ok;
	}
	printf("%d\n",rez);
	return 0;
}