Cod sursa(job #1585291)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 30 ianuarie 2016 21:58:28
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <list>

using namespace std;

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

const int bmax = 4000000;
char buffer[bmax];
int currIndex = 0;

void read(int &a) {

	a = 0;

	while (buffer[currIndex] < '0' || buffer[currIndex] > '9') {
		++currIndex;
		if (currIndex == bmax - 1) {
			fin.get(buffer, bmax, EOF);
			currIndex = 0;
		}
	}

	while (buffer[currIndex] >= '0' && buffer[currIndex] <= '9') {
		a = a * 10 + (buffer[currIndex] - '0');
		++currIndex;
		if (currIndex == bmax - 1) {
			fin.get(buffer, bmax, EOF);
			currIndex = 0;
		}
	}

}

const int mod = 100007;
const int base = 247307;

struct Hash {

	int x, y;

	Hash() {}

	Hash(int x, int y) {
		this->x = x;
		this->y = y;
	}

};

list< pair<int, int> > hashTable[mod];

int w, h;

bool check(int x, int y, int checkX, int checkY) {

	int currHash = (1LL * x * base + y) % mod;

	for (list< pair<int, int> >::iterator it = hashTable[currHash].begin(); it != hashTable[currHash].end(); ++it) {

		int xx = it->first, yy = it->second;

		if (xx <= checkX && checkX <= xx + w - 1 && yy <= checkY && checkY <= yy + h - 1)
			return true;

	}

	return false;

}

int main() {

	fin.get(buffer, bmax, EOF);

	int n, m;
	read(n); read(m); read(w); read(h);
	++w, ++h;

	for (int i = 1; i <= n; ++i) {

		int x, y;
		read(x); read(y);

		int xx = x, yy = y;

		x = ((x - 1) / w + 1 + (x % w == 0 ? 1 : 0)) * w - (x % w == 0 ? w : 0);
		y = ((y - 1) / h + 1 + (y % h == 0 ? 1 : 0)) * h - (y % h == 0 ? h : 0);

		int currHash = (1LL * x * base + y) % mod;

		hashTable[currHash].push_back(make_pair(xx, yy));

	}

	int sol = 0;

	for (int i = 1; i <= m; ++i) {

		int x, y;
		read(x); read(y);

		int xx = x, yy = y;

		x = ((x - 1) / w + 1 + (x % w == 0 ? 1 : 0)) * w - w;
		y = ((y - 1) / h + 1 + (y % h == 0 ? 1 : 0)) * h - h;

		if (check(x, y, xx, yy)) {
			++sol;
			continue;
		}

		x += w;

		if (check(x, y, xx, yy)) {
			++sol;
			continue;
		}

		y += h;

		if (check(x, y, xx, yy)) {
			++sol;
			continue;
		}

		x -= w;

		if (check(x, y, xx, yy)) {
			++sol;
			continue;
		}

	}

	fout << sol << '\n';

	return 0;

}

//Trust me, I'm the Doctor!