Cod sursa(job #474598)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 4 august 2010 13:13:22
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

#define file_in "ograzi.in"
#define file_out "ograzi.out"

#define mod1 31
#define mod2 67
#define mod 666013
#define nmax 50500

int n,m,h,w,l;
int q1[nmax];
int q2[nmax];
vector<int> hash[mod+20];
char s[20]; 


void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	int px,py,x,j;
	
	scanf("%d %d %d %d\n", &n, &m, &h, &w);
	for (int i=1;i<=n;++i)
	{
		fgets(s,20,stdin);
		l=strlen(s)-2;   
        for (j=0;s[j]!=' ';++j) 
			q1[i]=q1[i]*10+s[j]-'0';
        for (j++;j<=l;++j) 
			q2[i]=q2[i]*10+s[j]-'0';

		
		px=q1[i]/h;
		py=q2[i]/w;
		x=(mod1*px+mod2*py)%mod;
		hash[x].push_back(i);
	}
}

int verif(int x, int y,int X,int Y)
{
	int i,xx;
	xx=(mod1*x+mod2*y)%mod;
	for (i=0;i<hash[xx].size();++i)
		 if (q1[hash[xx][i]]<=X && q1[hash[xx][i]]+h>=X && 
			 q2[hash[xx][i]]<=Y && q2[hash[xx][i]]+w>=Y)
		return 1;
	return 0;
}	

void solve()
{
	int x,y,sol=0,px,py,j;
	for (int i=1;i<=m;++i)
	{
		fgets(s,20,stdin);
		l=strlen(s)-2;
        x=y=0;
        for (j=0;s[j]!=' ';++j) 
			x=x*10+s[j]-'0';
        for (j++;j<=l;++j) 
			y=y*10+s[j]-'0';

		
		px=x/h;
		py=y/w;
		
		if (verif(px,py,x,y) || verif(px-1,py,x,y) || verif(px,py-1,x,y) || verif(px-1,py-1,x,y))
			 sol++;
	}
	
	printf("%d\n", sol);
}


int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}