Cod sursa(job #42743)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 29 martie 2007 14:42:46
Problema Ograzi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#include <functional>
#include <ext/hash_map>

using namespace std;
using namespace __gnu_cxx;

#define MP make_pair
#define x first
#define y second

const int NDIR = 4;
const int dx[] = {0, 0, 1, 1};
const int dy[] = {0, 1, 0, 1};
const int VMAX = 100000;

int N, M, W, H;
hash_map <long long , long long> HS;

int toint(const char *s) {
	int rez = 0, i;

	for (i = 0; s[i]; ++i)
		rez = rez * 10 + (s[i] - '0');
}

long long tohash(int u, int v) {
	return (long long) u * VMAX + v;
}

int main(void) {
	FILE *fin = fopen("ograzi.in", "rt");
	FILE *fout = fopen("ograzi.out", "wt");
	
	int i, u, v, u1, v1, rez = 0;
	char buf[16];
	bool ok;
	long long c;

	fscanf(fin, " %d %d %d %d", &N, &M, &W, &H);

	for (i = 0; i < N; ++i) {
		fscanf(fin, " %s", buf);
		u = toint(buf);
		fscanf(fin, " %s", buf);
		v = toint(buf);

		HS[ tohash(u / W, v / H) ] = tohash(u, v);
	}

	for (i = 0; i < M; ++i) {
		fscanf(fin, " %s", buf);
		u = toint(buf);
		fscanf(fin, " %s", buf);
		v = toint(buf);

		u1 = u / W; v1 = v / H;
		
		ok = false;
		for (i = 0; i < NDIR && !ok; ++i) {
			c =  HS[ tohash(u1 + dx[i], v1 + dy[i]) ];

			if (c > 0 && u + W > c / VMAX && v + H > c % VMAX)
				ok = true;
		}

		if (ok) ++rez;
	}

	fprintf(fout, "%d\n", rez);

	fclose(fin);
	fclose(fout);
	return 0;
}