Cod sursa(job #2837014)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 21 ianuarie 2022 15:22:16
Problema Ograzi Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.13 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

#define x first
#define y second

ifstream fin("ograzi.in");
ofstream fout("ograzi.out");

const int mod = 40009, p = 107;
int n, m, lung, lat, ans, x, y;
vector <pair <int, int>> loc[mod];

string s;

int myHash(int a, int b)
{
    return (a * p + b) % mod;
}
void check(int nr, int a, int b)
{
    for(auto i : loc[nr])
    {
        if(i.x <= a && a <= i.x + lung && i.y <= b && b <= i.y + lat)
        {
            ans++;
        return;
        }
    }
}

void citire()
{
    getline(fin, s);
    s = s + ' ';
    int ind = 0, semn = 1, nr = 0;
    if(s[ind] == '-')
    {
        semn = -1;
        ind++;
    }
    while(s[ind] != ' ')
    {
        nr = nr * 10 + (s[ind] - '0');
        ind++;
    }
    n = semn * nr;
    ind++;
    semn = 1, nr = 0;
    if(s[ind] == '-')
    {
        semn = -1;
        ind++;
    }
    while(s[ind] != ' ')
    {
        nr = nr * 10 + (s[ind] - '0');
        ind++;
    }
    m = semn * nr;
    ind++;
    semn = 1, nr = 0;
    if(s[ind] == '-')
    {
        semn = -1;
        ind++;
    }
    while(s[ind] != ' ')
    {
        nr = nr * 10 + (s[ind] - '0');
        ind++;
    }
    lung = semn * nr;
    ind++;
    semn = 1, nr = 0;
    if(s[ind] == '-')
    {
        semn = -1;
        ind++;
    }
    while(s[ind] != ' ')
    {
        nr = nr * 10 + (s[ind] - '0');
        ind++;
    }
    lat = semn * nr;
    for(int i = 1; i <= n; i++)
    {
        getline(fin, s);
        s = s + ' ';
        int ind = 0, semn = 1, nr = 0;
        if(s[ind] == '-')
        {
            semn = -1;
            ind++;
        }
        while(s[ind] != ' ')
        {
            nr = nr * 10 + (s[ind] - '0');
            ind++;
        }
        x = semn * nr;
        ind++;
        semn = 1, nr = 0;
        if(s[ind] == '-')
        {
            semn = -1;
            ind++;
        }
        while(s[ind] != ' ')
        {
            nr = nr * 10 + (s[ind] - '0');
            ind++;
        }
        y = semn * nr;
        loc[myHash(x / lung + 1, y / lat + 1)].push_back({x, y});
    }



    for(int i = 1; i <= m; i++)
    {
        getline(fin, s);
        s = s + ' ';
        int ind = 0, semn = 1, nr = 0;
        if(s[ind] == '-')
        {
            semn = -1;
            ind++;
        }
        while(s[ind] != ' ')
        {
            nr = nr * 10 + (s[ind] - '0');
            ind++;
        }
        x = semn * nr;
        ind++;
        semn = 1, nr = 0;
        if(s[ind] == '-')
        {
            semn = -1;
            ind++;
        }
        while(s[ind] != ' ')
        {
            nr = nr * 10 + (s[ind] - '0');
            ind++;
        }
        y = semn * nr;
        check(myHash(x / lung + 1, y / lat + 1), x, y);
        check(myHash(x / lung, y / lat + 1), x, y);
        check(myHash(x / lung + 1, y / lat), x, y);
        check(myHash(x / lung, y / lat), x, y);
    }
    fout << ans;
}

int main()
{
    citire();
    return 0;
}