Cod sursa(job #295708)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 3 aprilie 2009 17:03:35
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include<stdio.h>
struct hash_info{int ii,jj,aa,bb;hash_info *next;};
hash_info *ht[50010],*paux;
int P=49999,n,m,A,B,dr,a,b,i,j,h,cnt,querry();
void readd(),solve();
int main()
{
	readd();
	solve();
	return 0;
}
void readd()
{
	freopen("ograzi.in","r",stdin);
	freopen("ograzi.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&A,&B);
	for(dr=1;dr<=n;dr++)
	{ 
		scanf("%d%d",&a,&b);a+=A;b+=B;
		i=a/A;if(a%A)i++;
		j=b/B;if(b%B)j++;
		h=(i+j)%P;
		paux=new hash_info;
		paux->ii=i;paux->jj=j;
		paux->aa=a;paux->bb=b;
		paux->next=ht[h];ht[h]=paux;
	}
}
void solve()
{
	for(;m;m--)cnt+=querry();
	printf("%d\n",cnt);
}
int querry()
{
	scanf("%d%d",&a,&b);a+=A;b+=B;
	i=(2*a-1)/(2*A);j=(2*b-1)/(2*B);
	h=(i+j)%P;
	for(paux=ht[h];paux;paux=paux->next)
	{
		if(paux->ii==i)
			if(paux->jj==j)
				if(paux->aa<=a)
					if(paux->bb<=b)
						if(paux->aa+A>=a)
							if(paux->bb+B>=b)
								return 1;
	}
	i++;
	h=(i+j)%P;
	for(paux=ht[h];paux;paux=paux->next)
	{
		if(paux->ii==i)
			if(paux->jj==j)
				if(paux->aa<=a)
					if(paux->bb<=b)
						if(paux->aa+A>=a)
							if(paux->bb+B>=b)
								return 1;
	}
	j++;
	h=(i+j)%P;
	for(paux=ht[h];paux;paux=paux->next)
	{
		if(paux->ii==i)
			if(paux->jj==j)
				if(paux->aa<=a)
					if(paux->bb<=b)
						if(paux->aa+A>=a)
							if(paux->bb+B>=b)
								return 1;
	}
	i--;
	h=(i+j)%P;
	for(paux=ht[h];paux;paux=paux->next)
	{
		if(paux->ii==i)
			if(paux->jj==j)
				if(paux->aa<=a)
					if(paux->bb<=b)
						if(paux->aa+A>=a)
							if(paux->bb+B>=b)
								return 1;
	}
	return 0;
}