Cod sursa(job #1333882)

Utilizator SmarandaMaria Pandele Smaranda Data 3 februarie 2015 18:05:15
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.59 kb
#include <cstdio>
#include <vector>
#include <unordered_map>

using namespace std;

const int N = 50003, M = 100003;

int n, m, w, h;

struct Dreptunghi {
    int x1, y1, x2, y2;
};

class Point {
    public :
        int x, y;
        bool operator == (const Point &other)const {
            return (this -> x == other.x && this -> y == other.y);
        }
};

const int H = 666013;

struct myHash {
    size_t operator () (const Point &A) const {
        size_t value = 1;
       /* value = value * H + hash <int>()(A.x);
        value = value * H + hash <int>()(A.y);*/
        value = (51 + hash <int> ()(A.x)) * 51 + hash <int> ()(A.y);
        return value;
    }
};

Dreptunghi D [N], R, temp;
unordered_map <Point, vector <Dreptunghi>, myHash> Hash;

int main () {
    int i, x, y, X, Y, num = 0, flag;
    Point B, C;
    vector <Dreptunghi> :: iterator it;

    freopen ("ograzi.in", "r", stdin);
    freopen ("ograzi.out", "w", stdout);

    scanf ("%d%d%d%d", &n, &m, &w, &h);
    for (i = 1; i <= n; i ++) {
        scanf ("%d%d", &D [i].x1, &D [i].y1);
        D [i].x2 = D [i].x1 + w;
        D [i].y2 = D [i].y1 + h;
        if (D [i].x1 % w == 0 && D [i].y1 % h == 0) {
            B.x = D [i].x1;
            B.y = D [i].y1;
            Hash [B].push_back (D [i]);

            B.x = D [i].x1;
            B.y = D [i].y2;
            Hash [B].push_back (D [i]);

            B.x = D [i].x2;
            B.y = D [i].y1;
            Hash [B].push_back (D [i]);

            B.x = D [i].x2;
            B.y = D [i].y2;
            Hash [B].push_back (D [i]);
        }

        else
            if (D [i].x1 % w == 0) {
                B.x = D [i].x1;
                B.y = (D [i].y1 / h + 1) * h;
                Hash [B].push_back (D [i]);

                B.x = D [i].x2;
                B.y = (D [i].y1 / h + 1) * h;
                Hash [B].push_back (D [i]);
            }

            else
                if (D [i].y1 % h == 0) {
                    B.y = D [i].y1;
                    B.x = (D [i].x1 / w + 1) * w;
                    Hash [B].push_back (D [i]);

                    B.y = D [i].y2;
                    B.x = (D [i].x1 / w + 1) * w;
                    Hash [B].push_back (D [i]);
                }

                else {
                    B.x = (D [i].x1 / w + 1) * w;
                    B.y = (D [i].y1 / h + 1) * h;
                    Hash [B].push_back (D [i]);
                }

    }
    for (i = 1; i <= m; i ++) {
        scanf ("%d%d", &x, &y);
        B.x = x / w * w;
        B.y = y / h * h;
        flag = 0;
        for (it = Hash [B].begin (); it != Hash [B].end () && !flag; ++ it) {
            R = *it;
            if (x >= R.x1 && x <= R.x2 && y >= R.y1 && y <= R.y2)
                flag = 1;
        }

        B.y = B.y + h;
        for (it = Hash [B].begin (); it != Hash [B].end () && !flag; ++ it) {
            R = *it;
            if (x >= R.x1 && x <= R.x2 && y >= R.y1 && y <= R.y2)
                flag = 1;
        }

        B.x = B.x + w;
        B.y = B.y - h;
        for (it = Hash [B].begin (); it != Hash [B].end () && !flag; ++ it) {
            R = *it;
            if (x >= R.x1 && x <= R.x2 && y >= R.y1 && y <= R.y2)
                flag = 1;
        }

        B.y = B.y + h;
        for (it = Hash [B].begin (); it != Hash [B].end () && !flag; ++ it) {
            R = *it;
            if (x >= R.x1 && x <= R.x2 && y >= R.y1 && y <= R.y2)
                flag = 1;
        }
        num = num + flag;
    }
    printf ("%d\n", num);

    return 0;
}