Cod sursa(job #27253)

Utilizator gcosminGheorghe Cosmin gcosmin Data 6 martie 2007 11:57:32
Problema Ograzi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define LL unsigned long long
#define ff first
#define ss second
#define NRB 48

LL NR1;
LL NR2;

int N, M, W, H, jeg;

int nr1[1 << 17];
pair <int, int> hash1[1 << 17][3];
int nr2[1 << 17];
pair <int, int> hash2[1 << 17][3];

inline int srch(int x, int y, int md1, int md2)
{
	int i;

	for (i = 0; i < nr1[md1]; i++)
		if (x - W <= hash1[md1][i].ff && hash1[md1][i].ff <= x && y - H <= hash1[md1][i].ss && hash1[md1][i].ss <= y) return 1;

	for (i = 0; i < nr2[md2]; i++)
		if (x - W <= hash2[md2][i].ff && hash2[md2][i].ff <= x && y - H <= hash2[md2][i].ss && hash2[md2][i].ss <= y) return 1;

return 0;
}

inline LL trans(int x, int y) { return (LL) x / W + (LL) y / H * jeg; }
inline LL trans1(int x, int y) { return x + (LL) y * jeg; }

int main()
{
	int i, x, y;

	int md1, md2;

//	printf("%lf\n", (double) (sizeof(hash1) + sizeof(hash2)) / 1024 / 1024);
	
	freopen("ograzi.in", "r", stdin);
	freopen("ograzi.out", "w", stdout);
	
	scanf("%d %d %d %d", &N, &M, &W, &H);

	NR1 = (LL) 1231513223 * 151231;
	NR2 = (LL) 3256121233 * 4313515;

//	printf("%lld %lld\n", NR1, NR2);

	LL aux;

	jeg = 1000000 / W;

	for (i = 1; i <= N; i++) {
		scanf("%d %d", &x, &y);

		aux = trans(x, y);

		md1 = (aux * NR1) >> NRB;
		md2 = (aux * NR2) >> NRB;

		if (nr1[md1] == 3 && nr2[md2] == 3) {
			printf("0\n");
			return 0;
		}

		if (nr1[md1] <= nr2[md2]) hash1[md1][nr1[md1]++] = make_pair(x, y);
		else hash2[md2][nr2[md2]++] = make_pair(x, y);
	}

	int ww, hh, rez = 0;

	for (i = 1; i <= M; i++) {
		scanf("%d %d", &x, &y);

		ww = x / W; hh = y / H;

		md1 = (trans1(ww, hh) * NR1) >> NRB;
		md2 = (trans1(ww, hh) * NR2) >> NRB;
//		printf("%d %d\n", md1, md2);
		if (srch(x, y, md1, md2)) { rez++; continue; }

		md1 = (trans1(ww-1, hh) * NR1) >> NRB;
		md2 = (trans1(ww-1, hh) * NR2) >> NRB;
//		printf("%d %d\n", md1, md2);
		if (srch(x, y, md1, md2)) { rez++; continue; }

		md1 = (trans1(ww, hh-1) * NR1) >> NRB;
		md2 = (trans1(ww, hh-1) * NR2) >> NRB;
//		printf("%d %d\n", md1, md2);
		if (srch(x, y, md1, md2)) { rez++; continue; }

		md1 = (trans1(ww-1, hh-1) * NR1) >> NRB;
		md2 = (trans1(ww-1, hh-1) * NR2) >> NRB;
		if (srch(x, y, md1, md2)) { rez++; continue; }
	}

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

fclose(stdin);
fclose(stdout);
return 0;
}