Cod sursa(job #915472)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 15 martie 2013 01:32:19
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

const int MOD = 123331;
const int MAX_N = 50002;

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

inline void search(int t1, int t2)
{
    int L = (t1*100+t2) % MOD;

    for(int q = 0; q < v[L].size(); ++q)
    {
        int i = v[L][q];
        if(A[i][0] <= x && x <= A[i][0] + W && A[i][1] <= y && y <= A[i][1] + H)
            ++Res, q = v[L].size();
    }
}

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);
    for(int i = 1; i <= N; ++i)
    {
        fgets(S, 15, 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;
                    j = len;
                }
            }
        }

        A[i][0] = x, A[i][1] = y;
        int t1 = (x+W-1) / W, t2 = (y+H-1) / H;
        v[(t1*100+t2) % MOD].push_back(i);
    }

    for(int q = 1; q <= M; ++q)
    {
        fgets(S, 15, 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;
                    j = len;
                }
            }
        int t1 = (x+W-1)/W, t2 = (y+H-1)/H;
        search(t1, t2);
        search(t1, t2-1);
        search(t1-1, t2);
        search(t1-1, t2-1);
    }

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

    fclose(f);
    fclose(g);

    return 0;
}