Cod sursa(job #25407)

Utilizator butyGeorge Butnaru buty Data 4 martie 2007 12:29:40
Problema Ograzi Scor 50
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 2.1 kb
#include<stdio.h>
const int Nmax=50001;
const int Mmax=100001;
struct punct
{
    int x,y;
};
int N,M,W,H,NR;
punct P[Mmax];
int X[Nmax],Y[Nmax];
void cit()
{
    int i;
    freopen("ograzi.in","r",stdin);
    scanf("%d%d%d%d",&N,&M,&W,&H);
    for(i=1;i<=N;i++)
        scanf("%d%d",&X[i],&Y[i]);
    for(i=1;i<=M;i++)
        scanf("%d%d",&P[i].x,&P[i].y);
}
int cauta_dr(int li,int ls,int x)
{
    if(li<ls)
    {
        int k=(li+ls)/2;
        if(P[k].x>x)
            return cauta_dr(li,k,x);
        else if(P[k].x<x)
            return cauta_dr(k+1,ls,x);
        else
            return k;
        
    }
    else
        if(P[li].x>=x)
            return li;
    
}
int cauta_st(int li,int ls,int x)
{
    if(li<ls)
    {
        int k=(li+ls)/2;
        if(P[k].x>x)
            return cauta_st(li,k,x);
        else if(P[k].x<x)
            return cauta_st(k+1,ls,x);
        else
            return k;
        
    }
    else
        if(P[li].x>x)
            return li-1;
        else if(P[li].x==x)
            return li;
    
}
int etc(int i,int j)
{
    int i0=0,j0=-1,aux;
    punct ax;
    while(i!=j)
    {
        if(P[i].x>P[j].x)
        {
            ax=P[i];
            P[i]=P[j];
            P[j]=ax;
            aux=j0;
            j0=-i0;
            i0=-aux;
        }
        i+=i0;
        j+=j0;
    }
    return i;
}
void qsort(int li,int ls)
{
    if(li<ls)
    {
        int k=etc(li,ls);
        qsort(li,k-1);
        qsort(k+1,ls);
    }
}
void rez()
{
    int a,b,j,i;
    qsort(1,M);
    for(i=1;i<=N;i++)
    {
        a=cauta_dr(1,M,X[i]);
        j=a;
        while(P[j].x==P[a].x)
            j--;
        a=j+1;
        b=cauta_st(1,M,X[i]+W);
        j=b;
        while(P[j].x==P[b].x)
            j++;
        b=j-1;
        for(j=a;j<=b;j++)
            if(Y[i]<=P[j].y&&Y[i]+H>=P[j].y)
                NR++;
    }
}
void scr()
{
    freopen("ograzi.out","w",stdout);
    printf("%d\n",NR);
    fclose(stdout);
}
int main()
{
    cit();
    rez();
    scr();
    return 0;
}