Cod sursa(job #1404065)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 27 martie 2015 19:10:40
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <fstream>
#include <unordered_map>
#include <list>

#define lint long long int
using namespace std;

int n, m, w, h;
struct point {
    int x, y;

    point (int _x = 0, int _y = 0): x(x), y(y) {}

    inline lint hash_value () {
        return ((x / w) * 1000005ll + (y / h));
    }
};

unordered_map <lint, list <point> > Map;

inline bool search (list <point> &lista, const point &oaie) {
    for (list <point> :: iterator it = lista.begin(); it != lista.end(); it++)
        if (it -> x <= oaie.x && oaie.x <= it -> x + w && it -> y <= oaie.y && oaie.y <= it -> y + h)
            return true;
    return false;
}

inline bool inchis (const point &oaie) {
    point aux = oaie;

    //Try 1
    if (search(Map[aux.hash_value()], oaie))
        return true;

    //Try 2
    if (aux.x >= w) {
        aux.x -= w;

        if (search(Map[aux.hash_value()], oaie))
            return true;

        aux.x += w;
    }

    //Try 3
    if (aux.y >= h) {
        aux.y -= h;

        if (search(Map[aux.hash_value()], oaie))
            return true;

        aux.y += h;
    }

    //Try 4
    if (aux.x >= w && aux.y >= h) {
        aux.x -= w;
        aux.y -= h;

        if (search(Map[aux.hash_value()], oaie))
            return true;

        aux.y += h;
        aux.x += w;
    }

    return false;
}

int main()
{
    ifstream cin("ograzi.in");
    ofstream cout("ograzi.out");

    cin >> n >> m >> w >> h;

    point aux;
    for (int i = 1; i <= n; i++) {
        cin >> aux.x >> aux.y;
        Map[aux.hash_value()].push_back(aux);
    }

    int ans = 0;
    for (int i = 1; i <= m; i++) {
        cin >> aux.x >> aux.y;
        ans += inchis(aux);
    }

    cout << ans << '\n';

    cin.close();
    cout.close();
    return 0;
}