Cod sursa(job #26564)

Utilizator flo_demonBunau Florin flo_demon Data 5 martie 2007 18:46:12
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.48 kb
#include <vector>
#include <stdio.h>
#include <algorithm>

#define MAXN 50006
#define MAXM 100006
#define MAXC 1000006

using namespace std;

class Point {
public :
    int x;
    int y;
    
    Point() : x(0), y(0){ };
    Point(int _x, int _y) : x(_x), y (_y) { }; 
    
    bool operator< (Point right) const {
         return x < right.x; 
    };
};

class PointY {
public :
    int x;
    int y;
    
    PointY() : x(0), y(0){ };
    PointY(int _x, int _y) : x(_x), y (_y) { }; 
    
    bool operator< (PointY right) const {
         return y < right.y; 
    };
};

class segmentTree {
public :
    vector<vector<PointY> > T;
    vector<PointY> puncteY;
    
    int x1, y1, x2, y2; 
    
    segmentTree()  { };
    segmentTree(int n) { T.resize(2*(n+3)); }
    
    int query(int nod, int st, int dr, int a, int b, int aux);
    void build(int nod, int st, int dr);
};

int segmentTree::query(int nod, int st, int dr, int a, int b, int aux) {
    int m, t = 0;
    vector<PointY>::iterator  t1, t2;
    if ((a <= st) && (dr <= b)) 
    {
        t1 = upper_bound(T[nod].begin(), T[nod].end(), PointY(x1, y1));
        t2 = lower_bound(T[nod].begin(), T[nod].end(), PointY(x2, y2)); 
        return t1 - t2; 
    }
    else 
    {
        m = (st + dr) / 2;
        if (a <= m)
            t += query(2*nod, st, m, a, b, aux);
        if (b > m)
            t += query(2*nod+1, m + 1, dr, a, b, aux);
        return t;
    }
};

void segmentTree::build(int nod, int st, int dr) { 
     if (st == dr) 
         T[nod].push_back(puncteY[st]);
     else
     {
         build(nod*2, st, (st+dr)/2); 
         build(nod*2+1, (st+dr)/2 + 1, dr); 
         T[nod].resize(T[2*nod].size() + T[2*nod+1].size());
         merge(T[nod*2].begin(), T[nod*2].end(), T[nod*2+1].begin(), T[nod*2+1].end(), T[nod].begin());
     }
}

vector<Point> puncte;
int nrPcte, H, W;
int pcte_dreptunghi[MAXN][2];

int main()
{
    int n, x, y, m, x1, y1, x2, y2, x_st, x_dr;
    FILE *fin = fopen("ograzi.in", "r");
    FILE *fout = fopen("ograzi.out", "w");
    fscanf(fin, "%d%d%d%d", &m, &n, &W, &H);
    for (int i = 1; i <= m; ++i)
        fscanf(fin, "%d%d", &pcte_dreptunghi[i][0], &pcte_dreptunghi[i][1]);
    puncte.reserve(n+6);
    for (int i = 1; i <= n; ++i)
    {
        fscanf(fin, "%d%d", &x, &y);
        puncte.push_back(Point(x, y)); 
    }
    vector<Point>::iterator start = puncte.begin();
    vector<Point>::iterator end = puncte.end();
    sort(start, end);
    start = puncte.begin();
    end = puncte.end();
    segmentTree aI(100000); 
    aI.puncteY.reserve(n+6);
    for (; start != end; ++start)
        aI.puncteY.push_back(PointY((*start).x, (*start).y));
    aI.build(1, 0, n-1); 
    vector<Point>::iterator index_found;
    for (int i = 1; i <= m; ++i)
    {
        x1 = pcte_dreptunghi[i][0];
        y1 = pcte_dreptunghi[i][1] + H;
        x2 = pcte_dreptunghi[i][0] + W;
        y2 = pcte_dreptunghi[i][1];

        index_found = lower_bound(puncte.begin(), puncte.end(), Point(x1, y1));
        x_st = index_found - puncte.begin();

        index_found = upper_bound(puncte.begin(), puncte.end(), Point(x2, y2));
        x_dr = index_found - puncte.begin() - 1;

        aI.x1 = x1;
        aI.x2 = x2;
        aI.y1 = y1;
        aI.y2 = y2;
        
        nrPcte += aI.query(1, 0, n-1, x_st, x_dr, 0);
    } 
    fprintf(fout, "%d\n", nrPcte);
    fclose(fin);
    fclose(fout);
    
    return 0;
}