Cod sursa(job #42744)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 29 martie 2007 14:43:13
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 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 r1 = 6007;
const int r2 = 10301;

namespace __gnu_cxx {
	template<> struct hash<pair <int, int> >
	{ size_t operator()(pair <int, int> __x) const { return __x.first * r1 +  __x.second * r2; } };
}

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

hash_map <pair <int, int>, pair <int, int> > HS;

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

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

	return rez;
}

int main(void) {
	FILE *fin = fopen("ograzi.in", "rt");
	FILE *fout = fopen("ograzi.out", "wt");
	
	int N, M, W, H;
	int i, j, u, v, u1, v1, rez = 0;
	char buf[16];
	bool ok;
	hash_map <pair <int, int>, pair <int, int> > :: iterator it;

	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);

//		printf("%d %d\n", u, v);

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

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

//		printf("%d %d\n", u, v);

		u1 = u / W; v1 = v / H;
		
		ok = false;
		for (j = 0; j < NDIR && !ok; ++j) {
			it = HS.find( MP(u1 - dx[j], v1 - dy[j]) );
//			printf("%d => %d %d\n", j, c.x, c.y);

			if (it != HS.end() && u >= it->y.x && u <= it->y.x + W && v >= it->y.y && v <= it->y.y + H)
				ok = true;
		}

		if (ok) ++rez;
	}

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

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