Cod sursa(job #965090)

Utilizator tudorv96Tudor Varan tudorv96 Data 23 iunie 2013 12:31:52
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#include <vector>
#include <cassert>
using namespace std;

#define mod 19997
#define xx first
#define yy second

ifstream fin ("ograzi.in");
ofstream fout ("ograzi.out");

typedef pair <int, int> sektor;
typedef pair <sektor, int> ograda;
typedef vector <ograda> :: iterator IT;

vector <ograda> H[mod];
int n, m, w, h, sol;
sektor v[50005];
char S[1 << 20], *now;

const int dw [] = {0, 1, 0, 1},
		  dh [] = {0, 0, 1, 1};

void parsare() {
	if (*now == 0) {
		fin.get (S, 1 << 20, '\0');
		now = S;
	}
}

int get() {
	int sol = 0;
	while (*now < '0' || *now > '9') {
		now++;
		parsare();
	}
	while (*now >= '0' && *now <= '9') {
		sol = sol * 10 + *now - '0';
		now++;
		parsare();
	}
	return sol;
}

int Hash(int x, int y) {
	return (x * 1000003LL + y) % mod;
} 
	  
int find(int sw, int sh) {
	sektor s = sektor(sw, sh);
	int k = Hash(sw, sh);
	assert (k >= 0 && k < mod);
	for (IT it = H[k].begin(); it != H[k].end(); ++it)
		if (s == it -> xx)
			return it -> yy;
	return 0;
}

void add(int x, int y, int i) {
	int k = Hash(x, y);
	assert (k >= 0 && k < mod);
	H[k].push_back (ograda (sektor (x, y), i));
}

int main() {
	now = S;
	parsare();
	n = get();
	m = get();
	w = get();
	h = get();
	for (int i = 1; i <= n; ++i) {
		v[i].xx = get();
		v[i].yy = get();
		add (v[i].xx / w + 1, v[i].yy / h + 1, i);
	}
	for (int i = 0; i < m; ++i) {
		int x, y;
		x = get();
		y = get();
		bool found = false;
		int sw = x / w, sh = y / h;
		for (int k = 0; k < 4; ++k) {
			int crt = find(sw + dw[k], sh + dh[k]);
			if (crt && x >= v[crt].xx && y >= v[crt].yy && x <= v[crt].xx + w && y <= v[crt].yy + h)
				found = 1;
		}
		sol += found;
	}
	fout << sol;
	fcloseall();
}