Cod sursa(job #41665)

Utilizator mastermageSchneider Stefan mastermage Data 28 martie 2007 14:21:51
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;

#define maxN 50100
#define maxHs 1100100

struct po{int x,y;po(){}po(int const&a,int const&b){x=a;y=b;}bool operator==(po const&r)const{return x==r.x && y==r.y;}bool operator<(po const&r)const{return x<r.x || (x==r.x && y<r.y);}};
typedef pair<po,po> per;

struct el{po v;el*n;el(){}el(po const&vp,el*const&np){v=vp;n=np;}};
void add(el*&p,po x){el*q=new el(x,p);p=q;}

int n,m,w,h,res;
po og[maxN];
el*hasht[maxHs];

int hs(int const&x,int const&y){
	return (x<<10+(y&(1<<10)))&(1<<20);
}

void getgr(int&x,int&y){
	x=x-x%w + w;
	y=y-y%h + h;
}

bool in(int const&x,int const&y, int const & px, int const& py){
	return x>=px && y>=py && x<=px+w && y<=py+h;
}

bool exist(int const&cx,int const&cy,int const&gx,int const&gy){
	for(el*i=hasht[hs(gx,gy)]; i;i=i->n){
		if(in(cx,cy,i->v.x,i->v.y))return 1;
	}
	return 0;
}

int main(){
	FILE*fi=fopen("ograzi.in","r"),*fo=fopen("ograzi.out","w");
	fscanf(fi,"%d %d %d %d",&n,&m,&w,&h);
	
	for(int i=0;i<n;i++){
		int x,y,gx,gy;fscanf(fi,"%d %d",&x,&y);og[i]=po(x,y);
		getgr(gx=x,gy=y);
		add(hasht[hs(gx,gy)],po(x,y));
	}
	
	
	for(int i=0;i<m;i++){
		int cx,cy,gx,gy;fscanf(fi,"%d %d",&cx,&cy);
		getgr(gx=cx,gy=cy);
		if(exist(cx,cy,gx,gy)){res++;continue;};
		gx-=w;
		if(exist(cx,cy,gx,gy)){res++;continue;};
		gx+=w;gy-=h;
		if(exist(cx,cy,gx,gy)){res++;continue;};
		gx-=w;
		if(exist(cx,cy,gx,gy)){res++;continue;};
	}
	
	fprintf(fo,"%d",res);fclose(fi);fclose(fo);return 0;
}