Cod sursa(job #159215)

Utilizator stef2nStefan Istrate stef2n Data 14 martie 2008 00:00:08
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

enum {START, POINT, END};
const int MAX_COORD = 1000000;
const int MAX_DIM = 2097152;

class event
{
    public:
        char type;
        int x, y;
        bool operator < (const event &A) const
        {
            if(x != A.x)
                return x < A.x;
            if(type != A.type)
                return type < A.type;
            return y < A.y;
        }
};

int N, M, W, H;
vector <event> E;
int cnt = 0;
bool T[MAX_DIM];
int A, B;

void read_data()
{
    event tmp;
    ifstream in("ograzi.in");
    in >> N >> M >> W >> H;
    for(int i = 0; i < N; ++i)
    {
        tmp.type = START;
        in >> tmp.x >> tmp.y;
        E.push_back(tmp);
        tmp.type = END;
        tmp.x += W;
        E.push_back(tmp);
    }
    for(int i = 0; i < M; ++i)
    {
        tmp.type = POINT;
        in >> tmp.x >> tmp.y;
        E.push_back(tmp);
    }
}

void mark(int n, int lo, int hi, const bool &value)
{
    if(A <= lo && hi <= B)
    {
        T[n] = value;
        return;
    }
    if(A <= (lo + hi) / 2)
        mark(2 * n, lo, (lo + hi) / 2, value);
    if(B > (lo + hi) / 2)
        mark(2 * n + 1, (lo + hi) / 2 + 1, hi, value);
}

bool query(int n, int lo, int hi, const int &p)
{
    if(T[n])
        return true;
    if(lo == hi)
        return false;
    if(p <= (lo + hi) / 2)
        return query(2 * n, lo, (lo + hi) / 2, p);
    else
        return query(2 * n + 1, (lo + hi) / 2 + 1, hi, p);
}

void solve()
{
    for(size_t i = 0; i < E.size(); ++i)
        switch(E[i].type)
        {
            case START:
                A = E[i].y;
                B = E[i].y + H;
                mark(1, 0, MAX_COORD, true);
                break;
            case END:
                A = E[i].y;
                B = E[i].y + H;
                mark(1, 0, MAX_COORD, false);
                break;
            default:
                cnt += query(1, 0, MAX_COORD, E[i].y);
                break;
        }
}


int main()
{

    read_data();
    sort(E.begin(), E.end());
    solve();
    ofstream out("ograzi.out");
    out << cnt << endl;
    return 0;
}