Cod sursa(job #326859)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 26 iunie 2009 14:29:09
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "ograzi.in"
#define file_out "ograzi.out"

#define Nmax 50100

struct coord
{
	int x1,y1;
}p[Nmax];

int n,nr,i,j,ok,xx,yy,w,h,m;

bool cmp(coord a, coord b)
{
	return (a.x1<b.x1);
}

int bs(int xx,int yy,int ls, int ld)
{
	int mij;
	
	while(ls<=ld)
	{
		mij=(ls+ld)>>1;
		
		if ((xx>=p[mij].x1 && xx<=p[mij].x1+w) &&
			(yy>=p[mij].y1 && yy<=p[mij].y1+h))
			return 1;
		else
		if (xx<=p[mij].x1 || yy<=p[mij].y1)
            return bs(xx,yy,ls,mij-1);
		else
		if (xx>=p[mij].x1+w || yy>=p[mij].y1+h)
            return bs(xx,yy,mij+1,ld);
	}
	
	return 0;
}

int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d %d %d", &n,&m,&w,&h);
	for (i=1;i<=n;++i)
		 scanf("%d %d", &p[i].x1,&p[i].y1);
	
	sort(p+1,p+n+1,cmp);
	
	nr=0;
	for (i=1;i<=m;++i)
	{
		scanf("%d %d", &xx,&yy);
		nr+=bs(xx,yy,1,n);
	}
	
	printf("%d", nr);
	
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}