Pagini recente » Cod sursa (job #554337) | Cod sursa (job #658870) | Cod sursa (job #254433) | Cod sursa (job #1812564) | Cod sursa (job #29680)
Cod sursa(job #29680)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAX_N 50005
#define MAX_H 65536
#define SHIFT 16
#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, lg, Res; point P[MAX_N]; char buf[64];
unsigned short hash1[MAX_H][4], hash2[MAX_H][4];
char size1[MAX_H], size2[MAX_H];
unsigned odd1, odd2;
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, h1, h2;
x = (((x<<1)|1)/(W<<1));
y = (((y<<1)|1)/(H<<1));
t = (((x>>10)^(y&1023))<<10)|((x&1023)^(y>>10));
h1 = (t * odd1) >> SHIFT;
h2 = (t * odd2) >> SHIFT;
if (size1[h1] < size2[h2])
hash1[h1][size1[h1]++] = idx;
else
hash2[h2][size2[h2]++] = idx;
}
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);
W2 = W<<1; H2 = H<<1;
srand(N^M^W^H);
odd1 = (rand()<<1)|1;
odd2 = (rand()<<1)|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;
x = (((x<<1)|1)/(W<<1));
y = (((y<<1)|1)/(H<<1));
t = (((x>>10)^(y&1023))<<10)|((x&1023)^(y>>10));
for (p = hash1[(t * odd1) >> SHIFT]; *p; p++)
if (included(P[0], P[*p]))
{
Res++;
break;
}
if (*p) continue;
for (p = hash2[(t * odd2) >> SHIFT]; *p; p++)
if (included(P[0], P[*p]))
{
Res++;
break;
}
}
printf("%d\n", Res);
return 0;
}