Cod sursa(job #2054667)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 2 noiembrie 2017 12:09:06
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <cstdio>
#include <cctype>

FILE *fin = fopen("ograzi.in", "r"), *fout = fopen("ograzi.out", "w");

#define BUF_SIZE 1 << 17

int pos = BUF_SIZE;
char buf[BUF_SIZE];

inline char nextch() {
    if (pos == BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), 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;
}

#define ll long long

#define MAXN 50000
#define MOD 666013

int k, a[MAXN + 1], b[MAXN + 1], next[MAXN + 1], lista[MOD];
ll val[MAXN + 1];
int w, h;
bool o;

inline ll conf(ll x, int y) {
    if (x < 0 || y < 0) return 0;
    else return (x << 30) + y;
}

inline bool este(int c, int x, int y) {
    if (c == 0 && !o) return 0;
    return (x - a[c] <= w && y - b[c] <= h && a[c] <= x && b[c] <= y);
}

inline void add(ll x, int u, int v) {
    int r = x % MOD;
    val[++k] = x;
    a[k] = u;
    b[k] = v;
    next[k] = lista[r];
    lista[r] = k;
}

inline int mp(ll x) {
    int p = lista[x % MOD];
    while (p != 0 && val[p] != x)
        p = next[p];
    return p;
}

int main() {
    int n = read();
    int m = read();
    w = read();
    h = read();

    for (int i = 0; i < n; i++) {
        int x = read();
        int y = read();

        add(conf(x / w, y / h), x, y);

        if (x == 0 && y == 0)
            o = 1;
    }

    int ans = 0;
    for (int i = 0; i < m; i++) {
        int x = read();
        int y = read();

        ans += este(mp(conf(x / w, y / h)), x, y) || este(mp(conf(x / w, y / h - 1)), x, y) || este(mp(conf(x / w - 1, y / h)), x, y) || este(mp(conf(x / w - 1, y / h - 1)), x, y);
    }

    fprintf(fout, "%d\n", ans);

    fclose(fin);
    fclose(fout);
    return 0;
}