Cod sursa(job #914793)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 14 martie 2013 14:07:03
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.25 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int MOD = 666013;
const int MAX_N = 50002;

typedef struct zona
{
    long long int nr;
    int o1, o2, o3, o4;
};

int N, M, W, H, x, y, MAX_W, MAX_H, Res;
int ograzi[ MAX_N ][2];
char S[105];
vector < zona > v[ MOD ];

inline void search(long long int nr, int o)
{
    int l = nr % MOD;

    for(int i = 0; i < v[l].size(); ++i)
        if(v[l][i].nr == nr)
        {
            if(v[l][i].o2 == -1)
                v[l][i].o2 = o;
            else if(v[l][i].o3 == -1)
                v[l][i].o3 = o;
            else v[l][i].o4 = o;

            return;
        }

    zona P;
    P.nr = nr, P.o1 = o, P.o2 = -1, P.o3 = -1, P.o4 = -1;
    v[l].push_back(P);
}

inline void add(int x, int y, int o)
{
    long long int nr = 0, t1 = 0, t2 = 0;
    zona P;


    t1 = x / W;
    if(x % W != 0)
        ++t1;
    t2 = y / H;
    if(y % H != 0)
        ++t2;

    nr = (long long) (t2 - 1) * MAX_W + t1;

    search(nr, o);
}



int main()
{
    FILE *f, *g;

    f = fopen("ograzi.in", "r");
    g = fopen("ograzi.out", "w");

    fscanf(f, "%d %d %d %d", &N, &M, &W, &H);
    fgets(S, 3, f);

    MAX_W = 1000000 / W;
    if(1000000 % W != 0)
        ++MAX_W;

    for(int q = 1; q <= N; ++q)
    {
        fgets(S, 100, f);

        int len = strlen(S) - 1;
        x = -1, y = -1;
        for(int i = 0; i < len; ++i)
        {
            if(S[i] >= '0' && S[i] <= '9')
            {
                if(x == -1)
                {
                    x = 0;
                    while(S[i] >= '0' && S[i] <= '9' && i < len)
                        x = x * 10 + S[i] - '0', ++i;
                }
                else
                {
                    y = 0;
                    while(S[i] >= '0' && S[i] <= '9' && i < len)
                        y = y * 10 + S[i] - '0', ++i;
                }
            }
        }
        ograzi[q][0] =  x, ograzi[q][1] = y;
        add(x, y, q);
        add(x+W, y, q);
        add(x, y+H, q);
        add(x+W, y+H, q);
    }

    for(int q = 1; q <= M; ++q)
    {
        fgets(S, 100, f);

        int len = strlen(S) - 1;
        x = -1, y = -1;
        for(int i = 0; i < len; ++i)
        {
            if(S[i] >= '0' && S[i] <= '9')
            {
                if(x == -1)
                {
                    x = 0;
                    while(S[i] >= '0' && S[i] <= '9' && i < len)
                        x = x * 10 + S[i] - '0', ++i;
                }
                else
                {
                    y = 0;
                    while(S[i] >= '0' && S[i] <= '9' && i < len)
                        y = y * 10 + S[i] - '0', ++i;
                }
            }
        }

        long long int t1 = 0, t2 = 0, nr = 0;

        t1 = x / W;
        if(x % W != 0)
            ++t1;
        t2 = y / H;
        if(y % H != 0)
            ++t2;

        nr = (long long) (t2 - 1) * MAX_W + t1;

        int l = nr % MOD;

        for(int i = 0; i < v[l].size(); ++i)
            if(v[l][i].nr == nr)
            {
                int o = v[l][i].o1;

                if(ograzi[o][0] <= x && x <= ograzi[o][0] + W && ograzi[o][1] <= y && y <= ograzi[o][1] + H)
                    ++Res;
                else if(v[l][i].o2 != -1)
                {
                    o = v[l][i].o2;
                    if(ograzi[o][0] <= x && x <= ograzi[o][0] + W && ograzi[o][1] <= y && y <= ograzi[o][1] + H)
                        ++Res;
                    else if(v[l][i].o3 != -1)
                    {
                        o = v[l][i].o3;
                        if(ograzi[o][0] <= x && x <= ograzi[o][0] + W && ograzi[o][1] <= y && y <= ograzi[o][1] + H)
                            ++Res;
                        else if(v[l][o].o4 != -1)
                        {
                            o = v[l][i].o4;
                            if(ograzi[o][0] <= x && x <= ograzi[o][0] + W && ograzi[o][1] <= y && y <= ograzi[o][1] + H)
                                ++Res;
                        }
                    }
                }
            }
    }

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

    fclose(f);
    fclose(g);

    return 0;
}