Cod sursa(job #715533)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 17 martie 2012 13:22:08
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<stdio.h>
#include<vector>

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

using namespace std;

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

int n,m,l,h,sol,found;
pair<int,int>A[maxn];
vector<int>H[mod+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 ;
		}			
	}
}

int main () {
	
	fscanf(f,"%d %d %d %d",&n,&m,&l,&h);
	
	for ( int i = 1 ; i <= n ; ++i ){
		int a,b; int x1,y1;
		fscanf(f,"%d %d",&x1,&y1); 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 ){
		fscanf(f,"%d %d",&x,&y);
		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;
}