Cod sursa(job #484470)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 14 septembrie 2010 16:48:45
Problema Ograzi Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#include <vector>
#define Nmax 50002
#define Mmax 100002
#define Prim1 37
#define Prim2 89
#define MOD 666013
#define pb push_back

using namespace std;

ifstream fin("ograzi.in");
ofstream fout("ograzi.out");

vector< int > H[MOD];
struct punct{int x,y; } D[Nmax];
int N,M,w,h,rez;

void search(int xx,int yy,int x,int y){
	vector< int >:: iterator it;
	int list=(xx*Prim1+yy*Prim2)%MOD;
	for(it=H[list].begin(); it!=H[list].end(); ++it)
		if( D[*it].x<=x && x<=D[*it].x+w && D[*it].y<=y && y<=D[*it].y+h ){
			rez++;
			return;
		}
}

int main(){
	int i,x,y,list;
	fin>>N>>M>>w>>h;
	for(i=1;i<=N;++i){
		fin>>D[i].x>>D[i].y;
		list=((D[i].x/w)*Prim1+(D[i].y/h)*Prim2)%MOD;
		H[list].pb(i);
	}
	
	for(i=1;i<=M;++i){
		fin>>x>>y;
		search(x/w,y/h,x,y);
		search(x/w-1,y/h,x,y);
		search(x/w,y/h-1,x,y);
		search(x/w-1,y/h-1,x,y);
	}
	
	fout<<rez<<"\n";
	fin.close(); fout.close();
	return 0;
}