Cod sursa(job #715606)

Utilizator ChallengeMurtaza Alexandru Challenge Data 17 martie 2012 15:20:25
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>
#include <vector>

using namespace std;

const char InFile[]="ograzi.in";
const char OutFile[]="ograzi.out";
const int HASH_MOD=666013;
const int dx[]={0,0,1,1};
const int dy[]={1,0,1,0};
const int MaxN=50111;

ifstream fin(InFile);
ofstream fout(OutFile);

struct Point
{
	int x,y;
};

int N,M,W,H,x,y,sol;
vector<int> Hash[HASH_MOD];
Point V[MaxN];

inline int HashFunc(const int &x, const int &y)
{
	return (x*211+y*307)%HASH_MOD;
}

inline bool PointInRectangle(const int &px, const int &py, const int &x1, const int &y1, const int &x2, const int &y2)
{
	if(px<x1)
	{
		return false;
	}
	if(x2<px)
	{
		return false;
	}
	if(py<y1)
	{
		return false;
	}
	if(y2<py)
	{
		return false;
	}
	return true;
}

inline bool HashFound(const int &px, const int &py)
{
	int key=HashFunc(px,py);
	for(vector<int>::iterator it=Hash[key].begin();it!=Hash[key].end();++it)
	{
		if(PointInRectangle(x,y,V[*it].x,V[*it].y,V[*it].x+W,V[*it].y+H))
		{
			return true;
		}
	}
	return false;
}

int main()
{
	fin>>N>>M>>W>>H;
	for(register int i=1;i<=N;++i)
	{
		fin>>x>>y;
		V[i].x=x;
		V[i].y=y;
		int px=(int)((x+W-0.5)/W),py=(int)((y+H-0.5)/H);
		Hash[HashFunc(px,py)].push_back(i);
	}
	for(register int i=1;i<=M;++i)
	{
		fin>>x>>y;
		int px=(int)((x-0.5)/W),py=(int)((y-0.5)/H);
		for(register int d=0;d<4;++d)
		{
			if(HashFound(px+dx[d],py+dy[d]))
			{
				++sol;
				break;
			}
		}
	}
	fin.close();

	fout<<sol;
	fout.close();
	return 0;
}