Cod sursa(job #995082)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 7 septembrie 2013 13:07:57
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

#define mod 19997
#define xx first
#define yy second

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

typedef pair <int, int> sektor;
typedef pair <sektor, int> ograda;
typedef vector <ograda> :: iterator IT;

vector <ograda> H[mod];
int n, m, w, h, sol;
sektor v[50005];
char S[1 << 20], *now;

const int dw [] = {0, 1, 0, 1},
          dh [] = {0, 0, 1, 1};

void parsare() {
    if (*now == 0) {
        fin.get (S, 1 << 20, '\0');
        now = S;
    }
}

int get() {
    int sol = 0;
    while (*now < '0' || *now > '9') {
        now++;
        parsare();
    }
    while (*now >= '0' && *now <= '9') {
        sol = sol * 10 + *now - '0';
        now++;
        parsare();
    }
    return sol;
}

int Hash(int x, int y) {
    return (x * 1000003LL + y) % mod;
}

int find(int sw, int sh) {
    sektor s = sektor(sw, sh);
    int k = Hash(sw, sh);
    assert (k >= 0 && k < mod);
    for (IT it = H[k].begin(); it != H[k].end(); ++it)
        if (s == it -> xx)
            return it -> yy;
    return 0;
}

void add(int x, int y, int i) {
    int k = Hash(x, y);
    assert (k >= 0 && k < mod);
    H[k].push_back (ograda (sektor (x, y), i));
}

int main() {
    now = S;
    parsare();
    n = get();
    m = get();
    w = get();
    h = get();
    for (int i = 1; i <= n; ++i) {
        v[i].xx = get();
        v[i].yy = get();
        add (v[i].xx / w + 1, v[i].yy / h + 1, i);
    }
    for (int i = 0; i < m; ++i) {
        int x, y;
        x = get();
        y = get();
        bool found = false;
        int sw = x / w, sh = y / h;
        for (int k = 0; k < 4; ++k) {
            int crt = find(sw + dw[k], sh + dh[k]);
            if (crt && x >= v[crt].xx && y >= v[crt].yy && x <= v[crt].xx + w && y <= v[crt].yy + h)
                found = 1;
        }
        sol += found;
    }
    fout << sol;
    fin.close();fout.close();
}