Pagini recente » Cod sursa (job #807199) | Cod sursa (job #524218) | Cod sursa (job #791958) | Cod sursa (job #1024446) | Cod sursa (job #2505121)
#include <bits/stdc++.h>
FILE *in = fopen("ograzi.in", "r"), *out = fopen("ograzi.out", "w") ;
const int MOD = 666013 ;
const int MV = 50000 ;
const int BUF_SIZE = (1 << 17) ;
using ll = long long ;
int pos = BUF_SIZE ;
char buf[BUF_SIZE] ;
inline char nextch() {
if (pos == BUF_SIZE) {
fread(buf, BUF_SIZE, 1, in) ;
pos = 0 ;
}
return buf[pos ++] ;
}
inline int read() {
char ch ;
while (!isdigit(ch = nextch())) ;
int x = ch - '0' ;
while (isdigit(ch = nextch())) { x = 10 * x + ch - '0' ; }
return x ;
}
int k, ord[MV + 1], absc[MV + 1], next[MV + 1], listord[MOD] ;
ll val[MV + 1] ;
int width, height ;
bool o ;
ll hash(ll x, int y) {
if (x < 0 || y < 0) { return 0 ; }
else {
return (x << 30) + y ;
}
}
bool este(int c, int x, int y) {
if (c == 0 && !o) { return 0 ; }
return (x - ord[c] <= width && y - absc[c] <= height && ord[c] <= x && absc[c] <= y) ;
}
void update(ll x, int u, int v) {
int r = x % MOD ;
val[++ k] = x ;
ord[k] = u ;
absc[k] = v ;
next[k] = listord[r] ;
listord[r] = k ;
}
int coresphash(ll x) {
int p = listord[x % MOD] ;
for ( ; p != 0 && val[p] != x ; p = next[p]) ; /// hashtable de mana ca suntem smekeri
return p ;
}
int main() {
int n = read() ;
int m = read() ;
width = read() ;
height = read() ;
for (int i = 0 ; i < n ; i++) {
int x = read() ;
int y = read() ;
update(hash(x / width, y / height), x, y) ; /// nu merge baleire :(
/// asa ca bag O(n + m) :)
}
int goodSheeps = 0 ;
for (int i = 0 ; i < m ; i++) {
int x = read() ;
int y = read() ;
goodSheeps += este(coresphash(hash(x / width, y / height)), x, y) |
este(coresphash(hash(x / width, y / height - 1)), x, y) |
este(coresphash(hash(x / width - 1, y / height)), x, y) |
este(coresphash(hash(x / width - 1, y / height - 1)), x, y) ;
}
fprintf(out, "%d\n", goodSheeps) ;
}