Pagini recente » Cod sursa (job #935890) | Cod sursa (job #1885525) | Cod sursa (job #951858) | Monitorul de evaluare | Cod sursa (job #25329)
Cod sursa(job #25329)
# 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;
}