Pagini recente » Cod sursa (job #1388931) | Cod sursa (job #1207662) | Cod sursa (job #1030803) | Cod sursa (job #48398) | Cod sursa (job #25152)
Cod sursa(job #25152)
#include <stdio.h>
#include <fstream>
#include <math.h>
using namespace std;
#define in "ograzi.in"
#define out "ograzi.out"
#define dim 50001
struct punct {
int x1, y1, x2, y2;
} p[dim];
int n, m, w, h;
void Qsorty(int,int);
int BinaryS(int,int);
int main()
{
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%d%d%d%d",&n,&m,&w,&h);
for ( int i = 1; i <= n; i++ )
{
scanf("%d%d",&p[i].x1,&p[i].y1);
p[i].x2 = p[i].x1+w;
p[i].y2 = p[i].y1+h;
}
Qsorty(1,n);
int t=0;
int x, y;
for ( int i = 1; i <= m; i++ )
{
scanf("%d%d",&x,&y);
if ( BinaryS(x,y) == 1 )
{
t+=1;
}
}
printf("%d", t);
}
void Qsorty(int st, int dr)
{
int i = st-1;
int j = dr+1;
int pivotx = p[st].x1;
int pivoty = p[st].y1;
while ( i <= j )
{
do { i++; } while ( pivoty > p[i].y1 || pivoty==p[i].y1 && pivotx > p[i].x1 );
do { j--; } while ( p[j].y1 > pivoty || pivoty==p[j].y1 && p[j].x1 > pivotx );
if ( i <= j )
{
punct aux = p[i];
p[i] = p[j];
p[j] = aux;
}
}
if ( st < j ) Qsorty(st,j);
if ( i < dr ) Qsorty(i,dr);
}
int BinaryS(int a,int b)
{
int st = 1;
int dr = n;
int ok = 0;
while ( st <= dr )
{
int mij = (st+dr)/2;
if ( p[mij].y1 > b )
{
dr = mij-1;
}
else
{
if ( p[mij].y2 < b )
{
st = mij + 1;
}
else
{
if ( p[mij].y1 <= b && p[mij].y2 >= b )
{
while ( p[mij].y1 <= b && p[mij].y2 >= b && ok == 0 )
{
if ( p[mij].x1 <= a && p[mij].y1 >= a )
{
ok = 1;
st = dr+1;
}
else
{
mij++;
}
}
if ( !ok )
{
while ( p[mij].y1 <= b && p[mij].y2 >= b && ok == 0 )
{
if ( p[mij].x1 <= a && p[mij].y1 >= a )
{
ok = 1;
st = dr+1;
}
else
{
mij++;
}
}
}
if ( !ok ) st = dr+1;
}
}
}
}
return ok;
}