Cod sursa(job #25135)

Utilizator cretuMusina Rares cretu Data 4 martie 2007 11:00:56
Problema Ograzi Scor 40
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.17 kb
#include <fstream>
#define MAX 50001

using namespace std;

int m, n, L, l, cnt = 0;
struct Punct{
       int x, y;
} p[MAX], o;

struct Comp{
       bool operator () (Punct x1, Punct x2)
       {
            if (x1.x == x2.x) return x1.y < x2.y;
            return x1.x < x2.x;
       }
};

void Search(int st, int dr);

int main()
{
    int i;
    ifstream fin("ograzi.in");
    fin >> n >> m >> L >> l;
    for (i = 1; i <= n; i++)    
        fin >> p[i].x >> p[i].y;
    sort(p+1, p+n+1, Comp());
    for (i = 1; i <= m; i++)    
    {
        fin >> o.x >> o.y;
        Search(1, n);    
    }
    fin.close();
    
    ofstream fout("ograzi.out");
    fout << cnt;
    fout.close();
    
    return 0;
}

void Search(int st, int dr)
{
    int q = (st+dr)/2;
    if (st > dr) return;
    if (p[q].x <= o.x && p[q].y <= o.y && o.x <= p[q].x + L && o.y <= p[q].y + l) 
    {
        cnt++;
        return;           
    }
    if (o.x == p[q].x)
    {
        Search(st, q-1);
        Search(q+1, dr);         
    }
    else 
    {
        if (o.x < p[q].x) Search(st, q-1);
        else              Search(q+1, dr);      
    }
}