Cod sursa(job #26495)

Utilizator sarabogdanSara Nicolae Bogdan sarabogdan Data 5 martie 2007 17:53:07
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include<stdio.h>


int n,m,w,h;

struct drept
{
       int x , y , x1 , y1;
};
int j;
drept a[50001];
drept aux;
int i ;
int oi[100001][3];
int k;
int li , ls,mij;
long sol = 0;
void poz(int li , int ls , int &k )
{
     
     long i = li , j = ls , i1 = 0 , j1 = -1 , c;
     
     
     while (i < j)
     {
           if (a[i].x > a[i+1].x || (a[i].x == a[i+1].x && a[i].x > a[i+1].y))
           {
                      aux = a[i];
                      a[i] = a[i+1];
                      a[i+1] = aux;
                      c = i1;
                      i1 = -j1;
                      j1 = -c;
           }
           i += i1;
           j += j1;
     }
     k = i;
}


void quick(int li,int ls)
{
     if (li<ls)
     {
               poz(li,ls,k);
               quick(li,k-1);
               quick(k+1,ls);
     }
}
int main()
{
    freopen("ograzi.in","r",stdin);
    freopen("ograzi.out","w",stdout);
    
    
    scanf("%d%d%d%d",&n,&m,&w,&h);
    
    for (i = 1 ; i <= n ; i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].x1 = a[i].x + w;
        a[i].y1 = a[i].y + h;
    }    
    for (i = 1 ; i <= m ; i++)
        scanf("%d%d",&oi[i][1],&oi[i][2]);
        
    quick(1,n);
    
    /*
    for (i = 1 ; i <= n ; i++)
    {
       printf("%ld %ld %ld %ld",a[i].x,a[i].y,a[i].x1,a[i].y1);
        printf("\n");
    }*/
    
    for (i = 1; i <= m ; i++)
    {
        
        li =1 , ls = n ;
        long k;
        while (li < ls)
        {
              mij = (li+ls)>>1;
              if (oi[i][1] > a[mij].x)
              {
                           li = mij+1;
                          
              }
              else
              if (oi[i][1] <=a[mij].x)
              {
                           ls =mij;
                          
              }
           
              
        }
        li = mij;
   //     printf("%ld %ld %ld\n",oi[i][1],oi[i][2],li);
        int ind = 1;
        for (j = mij,a[j].x1 >= oi[i][1] ; j <= n ; j++)
        {
         
            if (oi[i][1]  >= a[j].x && oi[i][1] <= a[j].x1 && oi[i][2] <= a[j].y1 && oi[i][2] >= a[j].y)
            {
                          ind = 0;
                          sol++;
                          break;
            }
         
        }
        if (ind ==1)
        {
            for (j = mij -1,a[j].x <= oi[i][1]; j >= 1 ; j--)
            if (oi[i][1]  >= a[j].x && oi[i][1] <= a[j].x1 && oi[i][2] <= a[j].y1 && oi[i][2] >= a[j].y)
            {
                          ind = 0;
                          sol++;
                          break;
            }
            
        }
        
        
    }
    printf("%d",sol);
    return 0;
}