Cod sursa(job #799692)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 19 octombrie 2012 20:52:55
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
#include<stdio.h>
#include<string.h>
#include<vector>

using namespace std;

#define MOD 50021
#define MAXN 50002

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

inline void 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][1], 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()
{
    FILE *f = fopen("ograzi.in", "r");

    fgets(S, 95, f);
    len = strlen(S) - 2;
    for(i = 0; i <= len; )
    {
        while( (S[i] == ' ' || S[i] == '\n') && i <= len)
            ++i;
        aux = 0;
        while(S[i] >= '0' && S[i] <= '9' && i <= len)
            aux = aux * 10 + S[i] - '0', ++i;
        if(aux)
        {
            if(!n)
                n = aux;
            else if(!m)
                m = aux;
            else if(!w)
                w = aux;
            else if(!h)
                h = aux;
        }
    }

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


    for( ; n; --n)
    {
        fgets(S, 95, f);
        len = strlen(S) - 2;
        x = y = 0;

        for(i = 0; i <= len; )
        {
            while( (S[i] == ' ' || S[i] == '\n') && i <= len)
                ++i;
            aux = 0;
            while(S[i] >= '0' && S[i] <= '9' && i <= len)
                aux = aux * 10 + S[i] - '0', ++i;
            if(aux)
            {
                if(!x)
                    x = aux;
                else y = aux;
            }
        }

        A[n][0] = x, A[n][1] = y;
        insert_value(n);

    }

    for( ; m; --m)
    {
        fgets(S, 95, f);
        len = strlen(S) - 2;
        x = y = 0;

        for(i = 0; i <= len; )
        {
            while( (S[i] == ' ' || S[i] == '\n') && i <= len)
                ++i;
            aux = 0;
            while(S[i] >= '0' && S[i] <= '9' && i <= len)
                aux = aux * 10 + S[i] - '0', ++i;
            if(aux)
            {
                if(!x)
                    x = aux;
                else y = aux;
            }
        }

        res += check(x, y);

    }

    fclose(f);

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

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

    fclose(g);

    return 0;
}