Pagini recente » Cod sursa (job #2015500) | Cod sursa (job #2393863) | Cod sursa (job #479519) | Cod sursa (job #1964552) | Cod sursa (job #29664)
Cod sursa(job #29664)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAX_N 50005
#define MAX_H 32768
#define SHIFT 17
#define FIN "ograzi.in"
#define FOUT "ograzi.out"
#define x first
#define y second
typedef pair<int, int> point;
int N, M, W, H, W2, H2, Res; point P[MAX_N]; char buf[64];
unsigned short hash[MAX_H][16]; char size[MAX_H]; unsigned odd;
inline point get(void)
{
int a, b; char *p;
fgets(buf, sizeof(buf), stdin);
for (p = buf, a = 0; *p >= '0' && *p <= '9'; p++)
a = a*10+ *p-'0';
for (; *p == ' '; p++);
for (b = 0; *p >= '0' && *p <= '9'; p++)
b = b*10 + *p-'0';
return make_pair(a, b);
}
inline void insert(int x, int y, int idx)
{
unsigned t, hval;
t = (((x<<1)|1)/(W<<1)) ^ (((y<<1)|1)/(H<<1));
hval = (t * odd) >> SHIFT;
hash[hval][size[hval]++] = idx;
while (size[hval] > 16);
}
inline int included(point p, point q)
{
return q.x <= p.x && p.x <= q.x+W && q.y <= p.y && p.y <= q.y+H;
}
int main(void)
{
int i, x, y, t;
unsigned short *p;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d %d %d %d\n", &N, &M, &W, &H);
srand(N+M+W+H);
odd = (rand()<<1)|1;
W2 = W<<1; H2 = H<<1;
for (i = 1; i <= N; i++)
{
P[i] = get();
insert(P[i].x, P[i].y, i);
insert(P[i].x+W, P[i].y, i);
insert(P[i].x, P[i].y+H, i);
insert(P[i].x+W, P[i].y+H, i);
}
for (i = 1; i <= M; i++)
{
P[0] = get();
x = P[0].first; y = P[0].second;
t = (((x<<1)|1)/(W<<1)) ^ (((y<<1)|1)/(H<<1));
for (p = hash[(t * odd) >> SHIFT]; *p; p++)
if (included(P[0], P[*p]))
{
Res++;
break;
}
}
printf("%d\n", Res);
return 0;
}