Cod sursa(job #1735977)

Utilizator leopop29Pop Leonard leopop29 Data 31 iulie 2016 19:11:06
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#define a first
#define b second
#define mp make_pair
#define NP 666013

using namespace std;


FILE* fin=fopen("ograzi.in","r");
const unsigned maxb=8192;
char buf[maxb];
unsigned ptr=maxb;

inline unsigned getInt(){
    unsigned nr=0;
    while(buf[ptr]<'0'||'9'<buf[ptr])
        if(++ptr>=maxb)
            fread(buf,maxb,1,fin),ptr=0;
    while('0'<=buf[ptr]&&buf[ptr]<='9'){
        nr=nr*10+buf[ptr]-'0';
        if(++ptr>=maxb)
            fread(buf,maxb,1,fin),ptr=0;
    }
    return nr;
}


int n, m, w, h;
vector<pair<int, int>> ht[NP];

inline void ins(pair<int, int> val)
{
    int x = val.a / w, y = val.b / h;

    ht[(1LL * x * 1000000 + y)%NP].push_back(val);
}

pair<int, int> query(pair<int, int> coord)
{
    if(coord.a < 0 || coord.b < 0)
        return mp(-1, -1);

    int key = (1LL * coord.a * 1000000 + coord.b)%NP;

    for(int i = 0; i < ht[key].size(); ++i)
    {
        if(ht[key][i].a/w == coord.a && ht[key][i].b/h == coord.b)
            return ht[key][i];
    }
    return mp(-1, -1);
}

inline bool ino(int x, int y)
{
    for(int i = 0; i <= 1; ++i)
        for(int j = 0; j <= 1; ++j)
        {
            pair<int, int> coord = query(mp(x/w - i, y/h - j));

            if(coord != mp(-1, -1))
                if((coord.a+w >= x && coord.b+h >= y) && (coord.a <= x && coord.b <= y))
                    return 1;
        }
    return 0;
}

int main()
{
    ofstream g("ograzi.out");

    n = getInt();
    m = getInt();
    w = getInt();
    h = getInt();

    for(int i = 1; i <= n; ++i)
    {
        int x, y;

        x = getInt();
        y = getInt();

        ins(mp(x, y));
    }

    int nr = 0;
    for(int i = 1; i <= m; ++i)
    {
        int x, y;

        x = getInt();
        y = getInt();

        nr += ino(x, y);
    }

    g << nr;
}