Cod sursa(job #316458)

Utilizator CezarMocanCezar Mocan CezarMocan Data 19 mai 2009 20:10:00
Problema Ograzi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#include <vector>
#define mod 131071
#define maxn 50100
#define maxm 100100
#define p1 69
#define p2 96

using namespace std;

struct punct {
	int x, y;
};

int n, m, w, h, i, j, z, sol;
punct v[maxn], x[maxm];
int ha[mod][30];
int nr[mod];

inline void baga(int x, int y) {
	double x1 = x, y1 = y;
	int zx, zy;

	zx = (int)((x1 - 0.5) / w);
	zy = (int)((y1 - 0.5) / h);

	int ct = (zx * p1 + zy * p2) & mod;
	nr[ct]++;
	ha[ct][nr[ct]] = i;
}

inline void get_hash(int x, int y, int &hs) {
	double x1 = x, y1 = y;
	int zx, zy;

	zx = (int)((x1 - 0.5) / w);
	zy = (int)((y1 - 0.5) / h);

	hs = (zx * p1 + zy * p2) & mod;
}

int main() {
	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].x, &v[i].y);
		baga(v[i].x, v[i].y);
		baga(v[i].x, v[i].y + h);
		baga(v[i].x + w, v[i].y);
		baga(v[i].x + w, v[i].y + h);
	}

	for (i = 1; i <= m; i++) {
		scanf("%d%d", &x[i].x, &x[i].y);
		int hs = 0;
		get_hash(x[i].x, x[i].y, hs);

		for (j = 1; j <= nr[hs]; j++) {
			z = ha[hs][j];
			if (x[i].x >= v[z].x && x[i].x <= v[z].x + w && x[i].y >= v[z].y && x[i].y <= v[z].y + h) {
				sol++;
//				printf("%d\n", i);
				break;
			}

		}
	}

	printf("%d\n", sol);

	return 0;
}