Cod sursa(job #879058)

Utilizator Marius96Marius Gavrilescu Marius96 Data 14 februarie 2013 22:12:38
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<cstdio>
#include<cstring>
#include<cctype>
#include<vector>
using std::vector;

static int x[50005];
static int y[50005];
static int w,h;

struct str
{
	int first,second;
};

inline str make_pair (int a,int b)
{
	str x;
	x.first=a;
	x.second=b;
	return x;
}

int g()
{
	int x;
	while(!isdigit (x=getchar()));
	int ret=x-'0';
	while(isdigit (x=getchar()))
		ret=ret*10+x-'0';

	return ret;
}

#define LEN 12415
#define PAIR str
#define inside(s,a,b) a<=s.first && a+w>=s.first && b<=s.second && b+h>=s.second
#define pack(s) ((s.first*13513+s.second)%LEN)
static vector<PAIR> hash[LEN];

#define BUFSIZE 1024*1024
static char buf[BUFSIZE];

int main (void)
{
	freopen ("ograzi.in","r",stdin);
#ifdef INFOARENA
	freopen ("ograzi.out","w",stdout);
#endif

	int n,m;
//	setvbuf (stdin, buf, _IOFBF, BUFSIZE);
	n=g();
	m=g();
	w=g();
	h=g();

	for(int i=0;i<n;i++){
		x[i]=g();
		y[i]=g();
	}

	for(int j=0;j<m;j++){
		int x,y;
		x=g();
		y=g();

		PAIR key=make_pair (x/w, y/h);
		hash[pack (key)].push_back (make_pair (x,y));
	}

	int ans=0;
	for(int i=0;i<n;i++){
		const int sa=x[i]/w;
		const int sb=y[i]/h;

		for(int a=sa;a<sa+2;a++)
			for(int b=sb;b<sb+2;b++){
				int key=pack (make_pair (a,b));
				for(std::vector<PAIR>::iterator it=hash[key].begin();it!=hash[key].end();it++)
					if(inside ((*it), x[i],y[i]))
						ans++;
			}
	}

	printf ("%d",ans);
	return 0;
}