Cod sursa(job #914805)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 14 martie 2013 14:31:49
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.04 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;

    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)
    {
        fscanf(f, "%d %d", &x, &y);

        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)
    {
        fscanf(f, "%d %d", &x, &y);

        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;
}