Pagini recente » Cod sursa (job #314990) | Cod sursa (job #637283) | Cod sursa (job #224216) | Cod sursa (job #1837096) | Cod sursa (job #25734)
Cod sursa(job #25734)
#include <stdio.h>
#include <algorithm>
#include <string.h>
#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];
char line[100];
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, j;
scanf("%d%d%d%d ", &n, &m, &w, &h);
for(i = 1; i <= n; ++i)
{
gets(line);
j = 0;
while(isdigit(line[j + 1]))
{
d[i].x += line[j] - '0';
d[i].x *= 10;
++j;
}
d[i].x += line[j] - '0';
j += 2;
while(isdigit(line[j + 1]))
{
d[i].y += line[j] - '0';
d[i].y *= 10;
++j;
}
d[i].y += line[j] - '0';
}
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;
}