Cod sursa(job #25845)

Utilizator cos_minBondane Cosmin cos_min Data 4 martie 2007 15:15:27
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.13 kb
#include <stdio.h>
#include <fstream>
#include <math.h>
using namespace std;

#define in "ograzi.in"
#define out "ograzi.out"
#define dim 50001

struct punct {
       int x1, y1, x2, y2;
} p[dim];

int n, m, w, h;

void Qsorty(int,int);
int BinaryS(int,int);

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d%d%d%d",&n,&m,&w,&h);
    
    for ( int i = 1; i <= n; i++ )
    {
        scanf("%d%d",&p[i].x1,&p[i].y1);
        p[i].x2 = p[i].x1+w;
        p[i].y2 = p[i].y1+h;
    }
    
    Qsorty(1,n);
    
   /* int k = sizeof(p);
    
    printf("%d\n",k);*/
    
    int t=0;
    int x, y;
    
    for ( int i = 1; i <= m; i++ )
    {
        scanf("%d%d",&x,&y);
        
        if ( BinaryS(x,y) == 1 )
        {
             t+=1;
        }
    }
    
    printf("%d", t);
}

void Qsorty(int st, int dr)
{
     int i = st-1;
     int j = dr+1;
     int pivotx = p[st].x1;
     int pivoty = p[st].y1;
     
     while ( i <= j )
     {
           do { i++; } while ( pivoty > p[i].y1  || pivoty==p[i].y1 && pivotx > p[i].x1 );
           do { j--; } while ( p[j].y1 > pivoty  || pivoty==p[j].y1 && p[j].x1 > pivotx );
           if ( i <= j )
           {
                punct aux = p[i];
                p[i] = p[j];
                p[j] = aux;
           }
     }
     
     if ( st < j ) Qsorty(st,j);
     if ( i < dr ) Qsorty(i,dr);
}

int BinaryS(int a,int b)
{
     int st = 1;
     int dr = n;
     int ok = 0;
     
     
    // printf("V : ");
     while ( st <= dr )
     {
           int mij = (st+dr)/2;
           
           if ( p[mij].y1 > b )
           {
                dr = mij-1;
           } 
           else
           {
               if ( p[mij].y2 < b )
               {
                    st = mij + 1;
               }
               else 
               {
                    if ( p[mij].y1 <= b && p[mij].y2 >= b )
                    {
                        // printf("%d ", mij);
                         int k = mij;
                         while ( p[k].y1 <= b && p[k].y2 >= b && ok == 0 )
                         {
                               if ( p[k].x1 <= a && p[k].x2 >= a )
                               {
                                    ok = 1;
                                    st = dr+1;
                               }
                               k++;
                         }
                         
                         if ( !ok )
                         {
                            while ( p[mij].y1 <= b && p[mij].y2 >= b && ok == 0 )
                            {
                               if ( p[mij].x1 <= a && p[mij].x2 >= a )
                               {
                                    ok = 1;
                                    st = dr+1;
                               }
                               mij--;
                            }
                         }
                         if ( !ok ) st = dr+1;
                    }
               }
           }
     }
     
     //printf("\n");
     
     return ok;
}