Cod sursa(job #915285)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 14 martie 2013 21:32:40
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>
#include <vector>
using namespace std;

const int MOD = 3019;
const int MAX_N = 50002;

typedef struct zona
{
    long long int nr;
    int og[5];
};

int N, M, W, H, x, y, Res;
int A[ MAX_N ][2];
long long int T;
vector < zona > v[ MOD + 2 ];

inline void Insert(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)
        {
            for(int j = 2; j <= 4; ++j)
                if(v[L][i].og[j] == -1)
                {
                    v[L][i].og[j] = o;
                    return;
                }
        }

   zona P;
   P.nr = nr, P.og[1] = o;
   for(int j = 2; j <= 4; ++j)
       P.og[j] = -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 + (x != 0 && x % W != 0);
    t2 = y / H + (y != 0 && y % H != 0);
    nr = (long long) ((t2 - 1) * T) + t1;
    Insert(nr, o);    
}

int main()
{
    ifstream f("ograzi.in");
    ofstream g("ograzi.out");

    f >> N >> M >> W >> H;

    T = 1000000 / W + (1000000 % W != 0);

    for(int i = 1; i <= N; ++i)
    {
        f >> x >> y;
        
        A[i][0] = x, A[i][1] = y;
        Add(x, y, i);
        Add(x+W, y, i);
        Add(x, y+H, i);
        Add(x+W, y+H, i);
    }

    for(int q = 1; q <= M; ++q)
    {
        f >> x >> y;

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

        t1 = x / W + (x != 0 && x % W != 0);
        t2 = y / H + (y != 0 && y % H != 0);
        nr = (long long) ((t2 - 1) * T) + t1;

     
        for(int i = 0, L = nr % MOD; i < v[L].size(); ++i)
            if(v[L][i].nr == nr)
            {
                for(int j = 1; j <= 4; ++j)
                {
                    if(v[L][i].og[j] == -1)
                        break;
                    else
                    {
                        int o = v[L][i].og[j];
                        if(o < 1 || o > N)
                            continue;
                        if(A[o][0] <= x && x <= A[o][0] + W && A[o][1] <= y && y <= A[o][1] + H)
                            ++Res, j = 4;
                    }
                }
            }
    }

    g << Res << '\n';

    f.close();
    g.close();

    return 0;
}