Cod sursa(job #28579)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 8 martie 2007 02:10:08
Problema Ograzi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 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) ((i>>10)^(i&1023))

int n,m,w,h,sol,T;
pair <int,int> P[nmax];
vector <int> A[1024][1024];

void Add(int x,int y,int i)
{
	x/=w,y/=h;
	x=g(x),y=g(y);
	A[x][y].pb(i);
	T>?=A[x][y].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,-1,1) FOR(jj,-1,1) 
	{
		i=p+ii,j=q+jj;
		if(j<0||i<0)
			continue;
		i=g(i),j=g(j);
		FOR(iii,0,A[i][j].sz)
			if(inside(x,y,A[i][j][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,0,n)
	{
		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",T);
	printf("%d\n",sol);
	return 0;
}