Cod sursa(job #877679)

Utilizator Marius96Marius Gavrilescu Marius96 Data 13 februarie 2013 01:44:58
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<tr1/unordered_map>
using std::make_pair;

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

#define PAIR std::pair<int,int>
#define MAP std::tr1::unordered_map<PAIR, std::vector<PAIR>, hash_pair>
#define IT MAP::iterator
#define inside(s,a,b) a<=s.first && a+w>=s.first && b<=s.second && b+h>=s.second

struct hash_pair
{
	int operator()(PAIR p)const
		{
			return std::tr1::hash<int>()(p.first)^std::tr1::hash<int>()(p.second);
		}
};

static MAP hash;

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

	int n,m;
	scanf ("%d%d%hd%hd\n",&n,&m,&w,&h);
	hash.max_load_factor (0.7);
	hash.rehash (m/0.7+5);

	char s[32];
	for(int i=0;i<n;i++){
		gets (s);
		x[i]=atoi (s);
		y[i]=atoi (strchr (s, ' ')+1);
	}

	for(int j=0;j<m;j++){
		short x,y;
		gets (s);
		x=atoi (s);
		y=atoi (strchr (s, ' ')+1);

		PAIR key=make_pair (x/w, y/h);
		IT it=hash.find (key);
		if(it!=hash.end())
			it->second.push_back (make_pair (x,y));
		else{
			std::vector<PAIR> value;
			value.push_back (make_pair (x,y));
			hash.insert (make_pair (key,value));
		}
	}

	int ans=0;
	for(int i=0;i<n;i++){
		const int sa=x[i]/w;
		const int sb=y[i]/h;
		std::pair<IT,IT> p;

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

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