Pagini recente » Cod sursa (job #1336816) | Cod sursa (job #140741) | Cod sursa (job #1194942) | Cod sursa (job #279730) | Cod sursa (job #2122837)
#include <fstream>
#include <algorithm>
using namespace std;
ofstream fout ("ograzi.out");
class InputReader {
public:
InputReader() {}
InputReader(const char *name) {
fin = fopen(name, "r");
buffpos = Size - 1;
}
inline InputReader &operator >>(int &n) {
char ch = nextpos();
while(ch < '0' || ch > '9') {
ch = nextpos();
}
n = 0;
while('0' <= ch && ch <= '9') {
n = n * 10 + ch - '0';
ch = nextpos();
}
return *this;
}
private:
FILE *fin;
static const int Size = 1 << 17;
int buffpos;
char buff[Size];
inline char nextpos() {
++ buffpos;
if(buffpos == Size) {
buffpos = 0;
fread(buff, Size, 1, fin);
}
return buff[ buffpos ];
}
} fin ("ograzi.in");
const int nmax = 1e5 + 5;
const int mmax = 5e4;
int n, m, cnt, n2;
struct pct {
int x, y;
inline bool operator < (const pct &shp) const {
return x < shp.x;
}
} v[nmax + 1], q[mmax + 1];
int aux[nmax + 1], valy[nmax + 1];
int aib[nmax + 1];
inline int lsb (int x) {
return x & -x;
}
void update (int pos, int val) {
for (int i = pos; i <= cnt; i += lsb( i ))
aib[ i ] += val;
}
int query (int pos) {
int sum = 0;
for (int i = pos; i > 0; i -= lsb( i ))
sum += aib[ i ];
return sum;
}
void normalizare_oi () {
for (int i = 1; i <= n; ++ i)
aux[ i ] = v[ i ].y;
sort(aux + 1, aux + n + 1);
cnt = 0;
for (int i = 1; i <= n; ) {
int j = i;
valy[ ++ cnt ] = aux[ i ];
while (j <= n && aux[ i ] == aux[ j ])
++ j;
i = j;
}
for (n2 = 1; (n2 << 1) <= cnt; n2 <<= 1) {
}
}
int bs (int val) {
int ans = cnt + 1;
for (int step = n2; step > 0; step >>= 1) {
if (ans - step > 0 && valy[ans - step] >= val)
ans -= step;
}
return ans;
}
int main () {
int dx, dy;
fin >> m >> n >> dx >> dy;
for (int i = 1; i <= m; ++ i) {
int x, y;
fin >> x >> y;
q[ i ].x = x, q[ i ].y = y;
}
for (int i = 1; i <= n; ++ i) {
fin >> v[ i ].x >> v[ i ].y;
}
normalizare_oi();
for (int i = 1; i <= n; ++ i) {
v[ i ].y = bs(v[ i ].y);
}
sort(v + 1, v + n + 1);
sort(q + 1, q + m + 1);
int bagate = 1, scoase = 1;
int ans = 0;
for (int i = 1; i <= n; ++ i) {
while (bagate <= m && q[ bagate ].x <= v[ i ].x) {
int x = bs(q[ bagate ].y);
update(x, 1);
x = bs(q[ bagate ].y + dy + 1);
update(x, -1);
++ bagate;
}
while (scoase <= m && q[ scoase ].x + dx + 1 <= v[ i ].x) {
int x = bs(q[ scoase ].y);
update(x, -1);
x = bs(q[ scoase ].y + dy + 1);
update(x, 1);
++ scoase;
}
if (query(v[ i ].y)) {
++ ans;
}
}
fout << ans << "\n";
fout.close();
return 0;
}