Cod sursa(job #965079)

Utilizator tudorv96Tudor Varan tudorv96 Data 23 iunie 2013 12:14:07
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <vector>
using namespace std;

#define mod 19997
#define MAX 1000003
#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[MAX];

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

int Hash(int x, int y) {
	return (x * MAX * 1LL + y) % mod;
} 
	  
int find(int sw, int sh) {
	sektor s = sektor(sw, sh);
	int k = Hash(sw, sh);
	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);
	H[k].push_back (ograda (sektor (x, y), i));
}

int main() {
	fin >> n >> m >> w >> h;
	for (int i = 1; i <= n; ++i) {
		fin >> v[i].xx >> v[i].yy;
		add (v[i].xx / w + 1, v[i].yy / h + 1, i);
	}
	for (int i = 0; i < m; ++i) {
		int x, y;
		fin >> x >> y;
		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();
}