Pagini recente » Cod sursa (job #512157) | Cod sursa (job #2989527) | Cod sursa (job #2119626) | Cod sursa (job #293161) | Cod sursa (job #25709)
Cod sursa(job #25709)
#include <stdio.h>
#include <algorithm>
#define nmax 1000000
using namespace std;
struct point
{
int x, y;
};
int n, m, w, h, sol, cnt;
point d[50001], o[100001], v[100001];
bool gasit(point);
bool cmpx(point one, point two)
{
return one.x < two.x || (one.x == two.x && one.y < two.y);
}
bool cmpy(point one, point two)
{
return one.y < two.y ||(one.y == two.y && one.x < two.x);
}
int main()
{
freopen("ograzi.in","r",stdin);
freopen("ograzi.out","w",stdout);
int i;
scanf("%d%d%d%d", &n, &m, &w, &h);
for(i = 1; i <= n; ++i)
{
scanf("%d%d", &d[i].x, &d[i].y);
}
sort(d + 1, d + n + 1, cmpx);
for(i = 1; i <= m; ++i)
{
scanf("%d%d", &o[i].x, &o[i].y);
if(gasit(o[i]))
{
++sol;
}
}
printf("%d", sol);
return 0;
}
bool gasit(point p)
{
int min = 1, mid, max = n, start = -1;
while(min <= max)
{
mid = (min + max) / 2;
if(p.x < d[mid].x)
{
max = mid - 1;
continue;
}
if(p.x > d[mid].x + w)
{
min = mid + 1;
continue;
}
if(p.x <= d[mid].x + w && p.x >= d[mid].x)
{
start = mid;
max = mid - 1;
}
}
if(start != -1)
{
while(cnt)
{
v[cnt].x = 0;
v[cnt].y = 0;
--cnt;
}
while(p.x <= d[start].x + w && p.x >= d[start].x)
{
v[++cnt] = d[start];
++start;
}
sort(v + 1, v + cnt + 1, cmpy);
min = 1;
max = cnt;
while(min <= max)
{
mid = (min + max) / 2;
if(v[mid].y <= p.y && v[mid].y + h >= p.y)
{
return 1;
}
if(v[mid].y < p.y)
{
min = mid + 1;
}
if(v[mid].y > p.y + h)
{
max = mid - 1;
}
}
return 0;
}
return 0;
}