Cod sursa(job #484542)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 14 septembrie 2010 19:32:49
Problema Ograzi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 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;
char s[102];

inline 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,j,x,y,list;
	fin>>N>>M>>w>>h; fin.getline(s,100);
	for(i=1;i<=N;++i){
		//fin>>D[i].x>>D[i].y;
		x=y=0;
		fin.getline(s,100);
		for(j=0; s[j]!=' '; ++j) x=x*10+s[j]-'0'; ++j;
		for( ; s[j]!='\0' && s[j]!='\n'; ++j) y=y*10+s[j]-'0';
		D[i].x=x; D[i].y=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;
		x=y=0;
		fin.getline(s,100);
		for(j=0; s[j]!=' '; ++j) x=x*10+s[j]-'0'; ++j;
		for( ; s[j]!='\0' && s[j]!='\n'; ++j) y=y*10+s[j]-'0';
		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;
}