Cod sursa(job #715537)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 17 martie 2012 13:25:23
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<stdio.h>
#include<vector>

#define maxn 50005
#define mod 500009
#define pb push_back
#define mp make_pair
#define file_size 3500000

using namespace std;

FILE*f=fopen("ograzi.in","r");
FILE*g=fopen("ograzi.out","w");

int n,m,l,h,sol,found,ch;
pair<int,int>A[maxn];
vector<int>H[mod+5];
char buff[file_size+5];

inline int get_hash ( int a , int b ){
	int h = (a*293 + b*307)%mod;
	return h;
}

inline void check ( int a , int b , int x , int y ){
	int list = get_hash(a,b);
	int u;
	
	for ( vector<int>::iterator itt = H[list].begin() ; itt != H[list].end() ; ++itt ){
		u = (*itt);
		if ( A[u].first <= x && A[u].second <= y && A[u].first+l >= x && A[u].second+h >= y ){
			++sol; found = 1;
			return ;
		}			
	}
}

inline int next () {
	int r = 0;
	
	++ch;
	while(buff[ch] >= '0' && buff[ch] <= '9' ){
		r = r * 10 + buff[ch] - '0';
		++ch;
	}
	
	return r;
}

int main () {
	
	fread(buff+1,file_size,1,f);
	n = next(); m = next(); l = next(); h = next();
	
	for ( int i = 1 ; i <= n ; ++i ){
		int a,b; int x1,y1;
		x1 = next(); y1 = next(); A[i] = mp(x1,y1);
		int x2,y2; x2 = x1 + l; y2 = y1 + h;
		
		a = (int)((x2-0.5)/l);
		b = (int)((y2-0.5)/h);
		
		H[get_hash(a,b)].pb(i);
	}
	
	int x,y;
	for ( int i = 1 ; i <= m ; ++i ){
		x = next(); y = next();
		int a,b;
		a = (int)((x-0.5)/l);
		b = (int)((y-0.5)/h);
		
		found = 0;
		
		check(a,b,x,y);
		if ( found )	continue ;
		check(a,b+1,x,y);
		if ( found )	continue ;
		check(a+1,b+1,x,y);
		if ( found )	continue ;
		check(a+1,b,x,y);
	}
	
	fprintf(g,"%d\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}