Cod sursa(job #1404121)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 27 martie 2015 19:56:15
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <fstream>
#include <unordered_map>
#include <cstring>
#include <cctype>
#include <list>

#define mod 666013
#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 int hash_value () {
        return (((x / w) * 1000005ll + (y / h)) % mod);
    }
};

list <point> hashes[mod];

inline void insert (point &drept) {
    hashes[drept.hash_value()].push_back(drept);
}

inline bool search (int b, const point &oaie) {
    for (list <point> :: iterator it = hashes[b].begin(); it != hashes[b].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(aux.hash_value(), oaie))
        return true;

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

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

        aux.x += w;
    }

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

        if (search(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(aux.hash_value(), oaie))
            return true;

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

    return false;
}

char sir[2300005];
int lung, poz;

ifstream cin("ograzi.in");
inline void get () {
    cin.get(sir + 1, 2300005, '#');
    lung = strlen(sir + 1);
    poz = 1;
}

inline int extr () {
    while (poz <= lung && !isdigit(sir[poz]))
        poz ++;

    int ans = 0;
    while (poz <= lung && isdigit(sir[poz])) {
        ans *= 10;
        ans += (sir[poz ++] - '0');
    }

    return ans;
}

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

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

    cin.get();
    get();

    point aux;
    for (int i = 1; i <= n; i++) {
        //cin >> aux.x >> aux.y;
        aux.x = extr();
        aux.y = extr();

        insert(aux);
    }

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

        ans += inchis(aux);
    }

    cout << ans << '\n';

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