Cod sursa(job #31269)

Utilizator azotlichidAdrian Vladu azotlichid Data 15 martie 2007 18:48:24
Problema Ograzi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>

#define ALL(x) (x).begin(), (x).end()
#define CLEAR(X) (memset(X, 0, sizeof(X)))
#define FORI(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define FOR(i, N, M) for (int i = (int)(N); i <= (int)(M); ++i)
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SIZE(X) (int)((X).size())
#define TIPA(a, i) (cerr << #a << "[" #i " = " << (i) << "] = " << (a)[i] << endl)
#define TIP(x) (cerr << #x << " = " << (x) << endl)

#define MP make_pair
#define PB push_back
#define INF 0x3f3f3f3f

typedef long long LL;

using namespace std;

int M, N, W, H, x, y, z, Ans = 0;
vector<pair<int, pair<int, int> > > e;  // x tip y
set<int> S;
set<int> :: iterator jt;

int main(void)
{
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    scanf("%d %d %d %d", &N, &M, &W, &H);
    REP(i, N)
    {
        scanf("%d %d", &x, &y);
        e.PB(MP(x, MP(0, y)));
        e.PB(MP(x+W, MP(2, y)));
    }

    REP(i, M)
    {
        scanf("%d %d", &x, &y);
        e.PB(MP(x, MP(1, y)));
    }
    
    sort(ALL(e));
    FORI(it, e)
    {
        z = (*it).second.second;
        switch((*it).second.first)
        {
            case 0:
                S.insert(z);
                break;
            case 1:
                jt = S.lower_bound(z-H);
                if (jt != S.end() && *jt <= z)
                    ++ Ans;
                break;
            case 2:
                S.erase(z);
                break;
        }
    }

    printf("%d\n", Ans);
    return 0;
}