Cod sursa(job #799573)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 19 octombrie 2012 13:53:50
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<stdio.h>
#include<fstream>
#include<vector>

using namespace std;

const int MOD = 666013, MAXN = 50002;

vector < long long int > v[ MOD ];
int A[ MAXN ][2];
int n, m, w, h, x, y, i, res, X;

inline int insert_value(int nr)
{
    long long int l, zx, zy, z, x1, x2, y1, y2;
    x1 = A[nr][0], x2 = x1 + w;
    y1 = A[nr][0], y2 = y1 + h;

    // coltul 1
    zx = x1 / w;
    zy = y1 / h;

    z = zy * X + zx + 1;
    l = z % MOD;
    v[l].push_back(nr);

    // coltul 2
    zx = x1 / w;
    zy = y2 / h;

    z = zy * X + zx + 1;
    l = z % MOD;
    v[l].push_back(nr);

    // coltul 3
    zx = x2 / w;
    zy = y1 / h;

    z = zy * X + zx + 1;
    l = z % MOD;
    v[l].push_back(nr);

    // coltul 4
    zx = x2 / w;
    zy = y2 / h;

    z = zy * X + zx + 1;
    l = z % MOD;
    v[l].push_back(nr);
}

inline int check(int x, int y)
{
    long long int l, zx, zy, z, i, nr;

    zx = x / w;
    zy = y / h;

    z = zy * X + zx + 1;
    l = z % MOD;

    for(i = 0; i < v[l].size(); ++i)
    {
        nr = v[l][i];
        if(x >= A[nr][0] && x <= A[nr][0] + w && y >= A[nr][1] && y <= A[nr][1] + h)
            return 1;
    }
    return 0;

}
int main()
{
    ifstream f("ograzi.in");

    f >> n >> m >> w >> h;

    X = 1000000 / w;
    if(1000000 % w)
        ++X;


    int zx;
    for(i = 1; i <= n; ++i)
    {
        f >> A[i][0] >> A[i][1];
        insert_value(i);
    }

    for(i = 1; i <= m; ++i)
    {
        f >> x >> y;
        res += check(x, y);
    }

    f.close();

    FILE *g = fopen("ograzi.out", "w");

    fprintf(g, "%d\n", res);

    fclose(g);
}