Cod sursa(job #785545)

Utilizator danalex97Dan H Alexandru danalex97 Data 9 septembrie 2012 13:25:48
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <vector>
using namespace std;

const int Pars = 1500010;
const int Hsize = 193939;
const int Hsexion = 97;

ifstream F("ograzi.in");
ofstream G("ograzi.out");

char Str[Pars];int Act;

void Get(int& A)
{
	while ( Str[Act]<'0' || Str[Act]>'9' ) ++Act;
	while ( Str[Act]>='0' && Str[Act]<='9' ) A=A*10+Str[Act++]-'0';
}

int N,M,W,H,Rez;

#define x first
#define y second

typedef pair<int,int> Pair;
typedef vector< Pair >::iterator Iter;
vector< Pair > Hash[Hsize];

inline int Hashing(int a,int b)
{	return (a*Hsexion+b)%Hsize; }

int Find(int a,int b,int A,int B)
{
	int Place = Hashing(a,b);
	for ( Iter it=Hash[Place].begin();it!=Hash[Place].end();++it)
		if ( (it->x)<=A && (it->x)+W>=A && (it->y)<=B && (it->y)+H>=B )
			return 1;
	return 0;
}

int main()
{
	F.getline(Str,Pars,EOF);
	
	Get(N), Get(M);
	Get(W), Get(H);
	
	for (int i=1;i<=N;++i)
	{
		int x=0, y=0;
		Get(x), Get(y);
		
		int a=(x+W-1)/W;
		int b=(y+H-1)/H;
		
		Hash[ Hashing( a , b ) ].push_back( make_pair(x,y) );
	}
	
	while ( M-- )
	{
		int  A=0 , B=0;
		Get(A), Get(B);
		
		int a=(A+W-1)/W;
		int b=(B+H-1)/H;
		
		Rez+= Find(a,b,A,B) | Find(a,b-1,A,B) | Find(a-1,b,A,B) | Find(a-1,b-1,A,B) ;
	}		
	
	G<<Rez<<'\n';
}