Cod sursa(job #1734122)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 26 iulie 2016 15:49:59
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#define NMAX 200006
#define INF 0x3f3f3f3f
#define pb push_back
#define MOD 30013

using namespace std;

typedef pair<int, int> pii;

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

vector<pii> Hash[MOD];

int h,w;
int dlin[4]={0,0,-1,-1};
int dcol[4]={0,-1,-1,0};
inline int hashval(int x, int y) {
	return (x*1000+y)%MOD;
}

inline bool find_hash(pii p) {
	int i,where;

	for(i=0;i<4;++i) {
		where=hashval(p.first/w+dlin[i],p.second/h+dcol[i]);

		if(where<0) continue;
		for(auto it:Hash[where])
			if(it.first<=p.first && p.first<=it.first+w && it.second<=p.second && p.second<=it.second+h) return 1;
	}

	return 0;
}

int main() {
	int n,m,i,x,y,nr=0;

	fin>>n>>m>>w>>h;
	for(i=0;i<n;++i) {
		fin>>x>>y;

		Hash[hashval(x/w,y/h)].pb({x,y});
	}

	for(i=0;i<m;++i) {
		fin>>x>>y;

		if(find_hash({x,y})) ++nr;
	}

	fout<<nr;

	return 0;
}