Cod sursa(job #42731)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 29 martie 2007 14:27:54
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 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

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

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;
	pair <int, int> 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);

//		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) {
			c = HS[ MP(u1 - dx[j], v1 - dy[j]) ];
//			printf("%d => %d %d\n", j, c.x, c.y);

			if (c.x > 0 && u >= c.x && u <= c.x + W && v >= c.y && v <= c.y + H)
				ok = true;
		}

		if (ok) ++rez;
	}

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

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