Cod sursa(job #25329)

Utilizator DorinOltean Dorin Dorin Data 4 martie 2007 12:01:25
Problema Ograzi Scor 10
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.33 kb
# include <stdio.h>

# define input "ograzi.in"
# define output "ograzi.out"

# define max 50001

long n,i,m,rez,x,y,W,H,j;

struct kkt
{
	long x1,y1,x2,y2;
}a[max];

long divide(long st,long dr)
{
	long x;
	kkt aux;
	aux = a[st];
	x = a[st].x1;
	while(st<dr)
	{
		while(st<dr && a[dr].x1 >= x) --dr;
		a[st] = a[dr];
		while(st<dr && a[st].x1 <= x)++st;
		a[dr] = a[st];
	}
	a[st] = aux;
	return st;
}

void qsort(long st,long dr)
{
	long mij = divide(st,dr);
	if(mij > st) qsort(st,mij-1);
	if(mij < dr) qsort(mij+1,dr);
}

void cauta(long x,long y)
{
	long st = 1,dr = n,mij;
	while(st<dr)
	{
		mij = (st+dr)>>1;
		if(a[mij].x1 >= x)
			dr = mij;
		if(a[mij].x1 < x)
			st = mij+1;
	}
	int ok = 0;
	for(j = mij;a[j].x2 >= x && j;--j)
	{
		if(a[j].y1 <= y && a[j].y2 >= y)
		{
			rez++;
			ok = 1;
			break;
		}
	}
	if(!ok)
	for(j = mij+1;a[j].x1 <= x && j;++j)
		if(a[j].y1 <= y && a[j].y2 >= y)
		{
			rez++;
			break;
		}
}

int main()
{
	freopen ( input,"r",stdin);
	freopen(output,"w",stdout);

	scanf("%ld%ld%ld%ld",&n,&m,&W,&H);

	for(i = 1;i<=n;++i)
	{
		scanf("%ld%ld",&a[i].x1,&a[i].y1);
		a[i].x2 = a[i].x1+W;
		a[i].y2 = a[i].y1+H;
	}

	qsort(1,n);

	for(i=1;i<=m;++i)
	{
		scanf("%ld%ld",&x,&y);
		cauta(x,y);
	}

	printf("%ld",rez);

	return 0;
}