Pagini recente » Cod sursa (job #1513952) | Cod sursa (job #1714608) | Cod sursa (job #885717) | Cod sursa (job #79620) | Cod sursa (job #1020965)
#include <cstdio>
#include <vector>
#include <utility>
using namespace std;
char buff[1<<15];
char * at;
const int MOD = 66013;
int n,m;
int w,h;
const int dx[] = {1, 0, -1};
const int dy[] = {1, 0, -1};
vector< pair<int, int> > hsh[MOD];
inline int key(const int x, const int y){
return (1LL * x * x * h + y * 3) % MOD;
}
void insert(const int x, const int y){
const int chain = key(x/w, y/h);
hsh[chain].push_back(make_pair(x, y));
}
bool search(const int x, const int y){
for(int i = 0 ; i < 3 ; ++i)for(int j = 0 ; j < 3 ; ++j){
const int new_x = x/w + dx[i],
new_y = y/h + dy[j];
const int chain = key(new_x, new_y);
for(unsigned int i = 0 ; i < hsh[chain].size() ; ++i){
const pair<int, int> now = hsh[chain][i];
if(now.first <= x && x <= now.first + w && now.second <= y && y <= now.second + h)
return 1;
}
}
return 0;
}
void next_char(){
++at;
if(at >= buff + sizeof(buff)){
fread(buff, sizeof(buff), 1, stdin);
at = buff;
}
}
const int next_int(){
int ret = 0;
while(*at && (*at < '0' || *at > '9'))
next_char();
while(*at >= '0' && *at <= '9'){
ret = ret * 10 + *at - '0';
next_char();
}
return ret;
}
int main(){
at = buff + (1 << 15);
freopen("ograzi.in", "r", stdin);
freopen("ograzi.out", "w", stdout);
n = next_int();
m = next_int();
w = next_int();
h = next_int();
int x,y;
for(int i = 0 ; i < n ; ++i){
x = next_int();
y = next_int();
insert(x, y);
}
int fnd = 0;
for(int i = 0 ; i < m ; ++i){
x = next_int();
y = next_int();
if(search(x, y))
++fnd;
}
printf("%d\n", fnd);
}