Cod sursa(job #1960953)

Utilizator BugirosRobert Bugiros Data 10 aprilie 2017 19:48:38
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int MODULO = 23013;
const int MAXDATE = 10000004;

vector<int> hashx[MODULO], hashy[MODULO];

int cheie_hash(int x, int y)
{
    return (x * 13 + y * 37) % MODULO;
}

char date[MAXDATE];
int pozdate;

int n, m, latime, inaltime;

void citirenumar(int &x)
{
    x = 0;
    while(!('0'<= date[pozdate] && date[pozdate] <= '9'))
        ++pozdate;
    while('0'<= date[pozdate] && date[pozdate] <= '9')
    {
        x = x * 10 + (date[pozdate] - '0');
        ++pozdate;
    }
}

void adauga(int a, int b, int x, int y)
{
    int cheie = cheie_hash(a,b);
    hashx[cheie].push_back(x);
    hashy[cheie].push_back(y);
}

bool exista(int a, int b, int x, int y)
{
    int cheie = cheie_hash(a,b);
    for (unsigned int i = 0;i < hashx[cheie].size();++i)
    {
        int X = hashx[cheie][i];
        int Y = hashy[cheie][i];
        if (X <= x && x <= X + latime && Y <= y && y <= Y + inaltime)
            return true;
    }
    return false;
}

void citire()
{
    in.get(date, MAXDATE, EOF);
    citirenumar(n);
    citirenumar(m);
    citirenumar(latime);
    citirenumar(inaltime);
    for (int i = 1;i <= n;++i)
    {
        int x1;
        citirenumar(x1);

        int x2 = x1 + latime;

        int a = x2 / latime;

        if (x2 < a * latime + 0.5)
            --a;
        if (a * latime + 0.5 < x1)
            ++a;



        int y1;
        citirenumar(y1);

        int y2 = y1 + inaltime;

        int b = y2 / inaltime;

        if (y2 < b * inaltime + 0.5)
            --b;
        if (b * inaltime + 0.5 < y1)
            ++b;


        adauga(a,b,x1,y1);
    }
}

int main()
{
    citire();
    int rasp = 0;
    for (int i = 1;i <= m;++i)
    {
        int x;
        citirenumar(x);

        int a = x / latime;
        if (x % latime == 0)
            --a;

        int y;
        citirenumar(y);

        int b = y / inaltime;
        if (y % inaltime == 0)
            --b;

        if (exista(a,b,x,y) || exista(a + 1, b, x, y) || exista(a, b + 1, x, y) || exista(a + 1, b + 1, x, y))
            ++rasp;
    }
    out << rasp << '\n';
    return 0;
}