Pagini recente » Cod sursa (job #263923) | Cod sursa (job #1370972) | Cod sursa (job #2597517) | Cod sursa (job #2796511) | Cod sursa (job #755593)
Cod sursa(job #755593)
#include <stdio.h>
#include <vector>
using namespace std;
#define MAX_N 50010
#define prim 131071
#define p1 103
#define p2 1
int n, m, w, h, i, j, sol;
struct dr {
int x1, y1, x2, y2;
} V[MAX_N];
struct punct {
int x, y;
} A[2 * MAX_N];
int H[prim + 1][16];
void cit() {
freopen("ograzi.in", "r", stdin);
freopen("ograzi.out", "w", stdout);
scanf("%d %d %d %d", &n, &m, &w, &h);
for (i = 1; i <= n; i++) {
scanf("%d %d", &V[i].x1, &V[i].y1);
V[i].x1++; V[i].y1++;
V[i].x2 = V[i].x1 + w;
V[i].y2 = V[i].y1 + h;
}
for (i = 1; i <= m; i++) {
scanf("%d %d", &A[i].x, &A[i].y);
A[i].x++; A[i].y++;
}
}
inline int poz_x(int p) {
if (p % w) return p / w + 1;
else return p / w;
}
inline int poz_y(int q) {
if (q % h) return q / h + 1;
else return q / h;
}
void add(int p, int q, int ind) {
p = poz_x(p);
q = poz_y(q);
int cell = (p * p1 + q * p2) % prim;
H[cell][++H[cell][0]] = ind;
}
void solve()
{
for (i = 1; i <= n; i++) {
add(V[i].x1, V[i].y1, i);
add(V[i].x1, V[i].y2, i);
add(V[i].x2, V[i].y1, i);
add(V[i].x2, V[i].y2, i);
}
for (i = 1; i <= m; i++) {
int p = poz_x(A[i].x);
int q = poz_y(A[i].y);
int cell = (p * p1 + q * p2) % prim;
int ok = 0;
for (j = 1; j <= H[cell][0]; j++) {
int dr = H[cell][j];
if (V[dr].x1 <= A[i].x && A[i].x <= V[dr].x2 && V[dr].y1 <= A[i].y && A[i].y <= V[dr].y2) {
ok = 1;
break;
}
}
if (ok) sol++;
}
printf("%d\n", sol);
}
int main() {
cit();
solve();
return 0;
}