Cod sursa(job #915306)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 14 martie 2013 21:42:27
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.4 kb
#include <fstream>
#include <vector>
#include <cstring>

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;
char S[105];
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()
{
    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);

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

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

        x = -1, y = 0;
        int len = strlen(S) - 1;
        for(int j = 0; j < len; ++j)
        {
            if(S[j] >= '0' && S[j] <= '9')
            {
                if(x == -1)
                {
                    x = 0;
                    while(S[j] >= '0' && S[j] <= '9' && j < len)
                        x = x * 10 + S[j] - '0', ++j;
                }
                else
                {
                    while(S[j] >= '0' && S[j] <= '9' && j < len)
                        y = y * 10 + S[j] - '0', ++j;
                }
            }
        }
        
        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)
    {
        fgets(S, 100, f);
        
        x = -1, y = 0;
        int len = strlen(S) - 1;
        for(int j = 0; j < len; ++j)
            if(S[j] >= '0' && S[j] <= '9')
            {
                if(x == -1)
                {
                    x = 0;
                    while(S[j] >= '0' && S[j] <= '9' && j < len)
                        x = x * 10 + S[j] - '0', ++j;
                }
                else
                {
                    while(S[j] >= '0' && S[j] <= '9' && j < len)
                        y = y * 10 + S[j] - '0', ++j;
                }
            }
        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;
                    }
                }
            }
    }

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

    fclose(f);
    fclose(g);

    return 0;
}