Cod sursa(job #1815760)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 25 noiembrie 2016 18:52:39
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("ograzi.in");
ofstream fout ("ograzi.out");

const int N = 10000000, mod = 666013;

int n, m, h, w, a, b, x, y, xj, yj, xs, ys, sol, mo, t, i;
char s[N];

vector<int> X[mod], Y[mod];

int valoare() {
    int x = 0;
    for (; s[t] <= '9' && s[t] >= '0'; ++t) {
        x = x * 10 + (s[t] - '0');
    }
    t++;
    return x;
}

void baga(int a, int b, int x, int y) {
    mo = (a * 13 + b * 37) % mod;
    X[mo].push_back(x);
    Y[mo].push_back(y);
}

int cauta(int a, int b) {
    mo = (a * 13 + b * 37) % mod;
    int siz = X[mo].size();
    siz--;
    for (int i = 0; i <= siz; ++i) {
        if (x >= X[mo][i] && y >= Y[mo][i] && x <= X[mo][i] + h && y <= Y[mo][i] + w) {
            return 1;
        }
    }
    return 0;
}

int main () {
    fin.get(s, N, EOF);
    n = valoare();
    m = valoare();
    w = valoare();
    h = valoare();
    swap(w, h);
    for (i = 1; i <= n; ++i) {
        xj = valoare();
        yj = valoare();
        xs = xj + h;
        ys = yj + w;
        a = xs / h;
        if (a * h + 0.5 > xs) {
            a--;
        }
        if(a * h + 0.5 < xj) {
            a++;
        }
        b = ys/w;
        if (b * w + 0.5 > ys) {
            b--;
        }
        if (b * w + 0.5 < yj) {
            b++;
        }
        baga(a, b, xj, yj);
    }
    for (i = 1; i <= n; ++i) {
        x = valoare();
        y = valoare();
        a = x / h;
        b = y / w;
        if (x % h == 0) {
            a--;
        }
        if (y % w == 0) {
            b--;
        }
        if (cauta(a, b) || cauta(a + 1, b) || cauta(a , b + 1) || cauta(a + 1, b + 1)) {
            sol++;
        }
    }
    fout << sol;
    return 0;
}