Cod sursa(job #2054704)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 2 noiembrie 2017 13:48:03
Problema Ograzi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <bits/stdc++.h>

FILE *fi, *fout;

const int MAXBUF = (1 << 17);

char buf[MAXBUF];
int pbuf = MAXBUF;

inline char nextch() {
    if(pbuf == MAXBUF) {
        fread(buf, 1, MAXBUF, fi);
        pbuf = 0;
    }
    return buf[pbuf++];
}

inline int getnr() {
    char ch = nextch();
    while(!isdigit(ch))
        ch = nextch();
    int nr = 0;
    while(isdigit(ch)) {
        nr = nr * 10 + ch - '0';
        ch = nextch();
    }
    return nr;
}

const int MAXN = (int) 5e4;

struct Rect {
    int x, y;
}r[MAXN + 1];

int w, h;

inline bool in(int x, int y, int p) {
    if(p == 0)
        return 0;
    return (r[p].x <= x && r[p].y <= y && x <= r[p].x + w && y <= r[p].y + h);
}

inline long long tr(int a, int b) {
    return (1LL * a << 30) + b;
}

const int MOD = 666013;

int ind[MOD];
long long val[MAXN + 1];
int nxt[MAXN + 1], pos[MAXN + 1];
int sz;

inline void add(long long x, int p) {
    int r = x % MOD;
    val[++sz] = x;
    pos[sz] = p;
    nxt[sz] = ind[r];
    ind[r] = sz;
}

inline int check(long long x) {
    int p = ind[x % MOD];
    while(p > 0 && val[p] != x)
        p = nxt[p];
    return pos[p];
}

int main() {
    int n, m, i, j, x, y;
    fi= fopen("ograzi.in" ,"r");
    fout = fopen("ograzi.out" ,"w");
    n = getnr();
    m = getnr();
    w = getnr();
    h = getnr();
    for(i = 1; i <= n; i++) {
        r[i].x = getnr();
        r[i].y = getnr();
        add(tr(r[i].x / w, r[i].y / h), i);
    }
    int ans = 0;
    for(i = 1; i <= m; i++) {
        x = getnr();
        y = getnr();
        if(in(x, y, check(tr(x / w - 1, y / h - 1))))
            ans++;
        else if(in(x, y, check(tr(x / w, y / h - 1))))
            ans++;
        else if(in(x, y, check(tr(x / w - 1, y / h))))
            ans++;
        else if(in(x, y, check(tr(x / w, y / h))))
            ans++;
    }
    fprintf(fout,"%d\n" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}