Cod sursa(job #1404053)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 27 martie 2015 19:05:32
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 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 inchis (const point &oaie) {
    list <point> :: iterator it;
    point aux = oaie;

    //Try 1
    for (it = Map[aux.hash_value()].begin(); it != Map[aux.hash_value()].end(); it++)
        if (it -> x <= oaie.x && oaie.x <= it -> x + w && it -> y <= oaie.y && oaie.y <= it -> y + h)
            return true;

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

        for (it = Map[aux.hash_value()].begin(); it != Map[aux.hash_value()].end(); it++)
            if (it -> x <= oaie.x && oaie.x <= it -> x + w && it -> y <= oaie.y && oaie.y <= it -> y + h)
                return true;

        aux.x += w;
    }

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

        for (it = Map[aux.hash_value()].begin(); it != Map[aux.hash_value()].end(); it++)
            if (it -> x <= oaie.x && oaie.x <= it -> x + w && it -> y <= oaie.y && oaie.y <= it -> y + h)
                return true;

        aux.y += h;
    }

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

        for (it = Map[aux.hash_value()].begin(); it != Map[aux.hash_value()].end(); it++)
            if (it -> x <= oaie.x && oaie.x <= it -> x + w && it -> y <= oaie.y && oaie.y <= it -> y + h)
                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;
}