Cod sursa(job #484551)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 14 septembrie 2010 20:00:13
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<stdio.h>
#include <vector>
#define Nmax 50002
#define Mmax 100002
#define Prim1 37
#define Prim2 89
#define MOD 666013
#define pb push_back

using namespace std;

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

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,lg;
	freopen("ograzi.in","r",stdin);
	freopen("ograzi.out","w",stdout);
	scanf("%d%d%d%d\n",&N,&M,&w,&h);
	for(i=1;i<=N;++i){
		fgets(s,100,stdin); lg=strlen(s); if(s[lg-1]=='\n') lg--;
		for(j=0; s[j]>='0' && s[j]<='9'; ++j) D[i].x=D[i].x*10+s[j]-'0'; 
		for(++j; j<lg; ++j) D[i].y=D[i].y*10+s[j]-'0';
		
		list=((D[i].x/w)*Prim1+(D[i].y/h)*Prim2)%MOD;
		H[list].pb(i);
	}
	
	for(i=1;i<=M;++i){
		fgets(s,100,stdin); lg=strlen(s); if(s[lg-1]=='\n') lg--;
		x=y=0;
		for(j=0; s[j]>='0' && s[j]<='9'; ++j) x=x*10+s[j]-'0'; 
		for(++j; j<lg; ++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);
	}
	
	printf("%d\n",rez);
	fclose(stdin); fclose(stdout);
	return 0;
}