Cod sursa(job #916072)

Utilizator cbanu96Banu Cristian cbanu96 Data 15 martie 2013 19:24:18
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <fstream>
#include <cstring>
#include <vector>

#define MOD 123331
#define NMAX 50002
#define FILEIN "ograzi.in"
#define FILEOUT "ograzi.out"

using namespace std;


int w,h,N,M,sol=0;
int x,y;
int V[NMAX][2];
char s[105];

vector<int> H[MOD];

inline int hashf(int a, int b)
{
    return (a * 100 + b)%MOD;
}

inline int search(int a, int b,int x, int y)
{
    int k = (a * 100 + b)%MOD;
    for ( int i = 0; i < H[k].size(); i++)
    {
        int p = H[k][i];
        if(V[p][0] <= x && x <= V[p][0] + w && V[p][1] <= y && V[p][1] + h)
        {
            sol++;
            return 1;
        }
    }
    return 0;
}

void parseread(int &k, int &l)
{
    fgets(s,15,stdin);
    int lg = strlen(s)-1;
    int i;
    k = l = -1;
    for ( i = 0 ; i < lg; i++)
    {
        if(s[i] >= '0' && s[i] <='9')
        {
            if ( k == -1 )
            {
                k = 0;
                while(s[i] >= '0' && s[i] <= '9' && i < lg)
                {
                    k = k * 10 + s[i] - '0';
                    i++;
                }
            }
            else
            {
                l = 0;
                while(s[i] >= '0' && s[i] <= '9' && i < lg)
                {
                    l = l * 10 + s[i] - '0';
                    i++;
                }
                i = lg;
            }
        }
    }
}

int main()
{
    int i, j, x1, y1;
    freopen(FILEIN,"r",stdin);
    freopen(FILEOUT,"w",stdout);
    scanf("%d %d %d %d", &N, &M, &w, &h);
    scanf("%c", &s[0]);
    for ( i = 1; i <= N; i++)
    {
        parseread(x,y);
        V[i][0] = x; V[i][1] = y;
        x1 = (x+w-1)/h;
        y1 = (y+h-1)/w;
        H[hashf(x1,y1)].push_back(i);
    }
    for ( i = 1; i <= M; i++)
    {
        parseread(x,y);
        x1 = (x+w-1)/w;
        y1 = (y+h-1)/h;
        search(x1,y1,x,y);
        search(x1,y1-1,x,y);
        search(x1-1,y1,x,y);
        search(x1-1,y1-1,x,y);
    }
    printf("%d\n", sol);
    return 0;
}