Cod sursa(job #28580)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 8 martie 2007 02:12:06
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define f first
#define s second
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define nmax 65536
#define sz size()
#define pb push_back
#define g(i,j) ((((i>>10)^(j&1023))<<10)|((j>>10)^(i&1023)))
#define BB 4

int n,m,w,h,sol,T;
pair <int,int> P[nmax];
short unsigned int A[1<<20][BB];

void Add(int x,int y,int i)
{
	x/=w,y/=h;
//	x=g(x),y=g(y);
	x=g(x,y);
	int ii;
	FOR(ii,0,BB)
		if(!A[x][ii])
		{
			A[x][ii]=i;
			break;
		}
//	A[x].pb(i);
//	T>?=A[x].sz;
}

int inside(int x,int y,int i)
{
	return P[i].f<=x&&P[i].f+w>=x&&P[i].s<=y&&P[i].s+h>=y;
}

int doit(int x,int y)
{
	int p=x/w,q=y/h,ii,jj,iii,i,j;
	FOR(ii,0,2) FOR(jj,0,2) 
	{
		i=p-ii,j=q-jj;
		if(j<0||i<0)
			continue;
//		i=g(i),j=g(j);
		i=g(i,j);
		FOR(iii,0,BB)
			if(!A[i][iii])
				break;
			else
				if(inside(x,y,A[i][iii]))
					return 1;
	}
	return 0;	
}

int poz;
char s[128];

int cit()
{
	int aux=0;
	for(;s[poz]>='0'&&s[poz]<='9';++poz)
		aux=aux*10+s[poz]-'0';
	poz++;
	return aux;
}

int main()
{
	freopen("ograzi.in","r",stdin);
	freopen("ograzi.out","w",stdout);
	int i,x,y;
	fgets(s,128,stdin);poz=0;
	n=cit(),m=cit(),w=cit(),h=cit();
	FOR(i,1,n+1)
	{
		fgets(s,128,stdin);poz=0;
		P[i].f=cit(),P[i].s=cit();
		Add(P[i].f,P[i].s,i);
	}
	FOR(i,0,m)
	{
		fgets(s,128,stdin);poz=0;
		x=cit(),y=cit();
		sol+=doit(x,y);//||doit(x-w,y)||doit(x,y-h)||doit(x-w,y-h);
	}
//	fprintf(stderr,"%d\n",sizeof(A)>>20);
	printf("%d\n",sol);
	return 0;
}