Cod sursa(job #1894306)

Utilizator OGEastBullOG EastBull OGEastBull Data 26 februarie 2017 18:52:46
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.19 kb
#include <bits/stdc++.h>

using namespace std;
ofstream fout("ograzi.out");
const int nmax = 100005;
int N,M,W,H,ans;


class InputReader {
    public:
        InputReader() {}
        InputReader(const char *file_name) {
            input_file = fopen(file_name, "r");
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
        inline InputReader &operator >>(int &n) {
            while(buffer[cursor] < '0' || buffer[cursor] > '9') {
                advance();
            }
            n = 0;
            while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
                n = n * 10 + buffer[cursor] - '0';
                advance();
            }
            return *this;
        }
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        int cursor;
        char buffer[SIZE];
        inline void advance() {
            ++ cursor;
            if(cursor == SIZE) {
                cursor = 0;
                fread(buffer, SIZE, 1, input_file);
            }
        }
};

struct oaie
{
    int x,y;
    bool operator < (const oaie &A) const
    {
        return y < A.y;
    }
};
oaie v[nmax];

struct drept
{
    int x1,x2,y1,y2,poz;
    bool operator < (const drept &A) const
    {
        return y1 < A.y1;
    }
};
drept a1[nmax];

set < int > S;
std::set<int>::iterator it,it2;

inline void Read()
{
    InputReader fin("ograzi.in");
    int i,x,y;
    fin >> N >> M >> W >> H;
    for(i = 1; i <= N; i++)
    {
        fin >> x >> y;
        a1[i].poz;
        a1[i].x1 = x; a1[i].y1 = y;
        a1[i].x2 = x + W; a1[i].y2 = y + H;
    }
    sort(a1+1,a1+N+1);
    for(i = 1; i <= M; i++)
    {
        fin >> v[i].x >> v[i].y;
    }
    sort(v+1,v+M+1);
}

inline bool Good(int p, int poz)
{
    return (v[p].y >= a1[poz].y1 && v[p].y <= a1[poz].y2);
}

inline void Solve()
{
    int i,p1,p2,x;
    bool ok;
    p1 = p2 = 1;
    while(p1 <= N && !Good(1,p1)) p1++;
    p2 = p1;
    if(p1 <= N) S.insert(a1[p1].x1);

    while(p2 + 1 <= N && Good(1,p2+1))
            {
                p2++;
                S.insert(a1[p2].x1);
            }
    for(i = 1; i <= M; i++)
    {
        while(p1 <= p2 && !Good(i,p1))
        {
            S.erase(S.find(a1[p1].x1));
            p1++;
        }
        if(p1 > p2)
        {
            while(p1 <= N && !Good(i,p1)) p1++;
            if(p1 <= N) S.insert(a1[p1].x1);
            p2 = p1;
            while(p2 + 1 <= N && Good(i,p2+1))
            {
                p2++;
                S.insert(a1[p2].x1);
            }
        }
        else
        {
            while(p2 + 1 <= N && Good(i,p2+1))
            {
                p2++;
                S.insert(a1[p2].x1);
            }
        }
        if(p1 <= p2 && p2 <= N)
        {
            it = S.end(); it--;
            if(v[i].x > *it + W) continue;
            it = S.upper_bound(v[i].x);
            if(it != S.begin()) it--;
            x = *it;
            if(x <= v[i].x && v[i].x <= x + W) ++ans;
        }
    }
    fout << ans << "\n";
}


int main()
{
    Read();
    Solve();
    fout.close();
    return 0;
}