Cod sursa(job #25844)

Utilizator cos_minBondane Cosmin cos_min Data 4 martie 2007 15:14:58
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.08 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], oi[dim];

int n, m, w, h;

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

int main()
{
    freopen(in,"r",stdin);
    
    FILE *fin = fopen("ograzi.in","r");
    freopen(out,"w",stdout);
    
    char line[21];
    int j = 0;
    int number=0;
    
    fscanf(fin,"%d%d%d%d",&n,&m,&w,&h);
    fscanf(fin,"\n");
    
    for ( int i = 1; i <= n; i++ )
    {
       fgets(line,20,fin);
       j=0;
       number=0;
       while(line[j]>='0' && line[j]<='9')
            {
             number=number*10+(line[j]-'0');
             j++;
            }
       p[i].x1=number;
       j++;
       number=0;
       while(line[j]>='0' && line[j]<='9')
            {
             number=number*10+(line[j]-'0');
             j++;
            }
       p[i].y1=number;
       
       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);*/
    
    for ( int i = 1; i <= m; i++ )
    {
       fgets(line,20,fin);
       j=0;
       number=0;
       while(line[j]>='0' && line[j]<='9')
            {
             number=number*10+(line[j]-'0');
             j++;
            }
       oi[i].x1=number;
       j++;
       number=0;
       while(line[j]>='0' && line[j]<='9')
            {
             number=number*10+(line[j]-'0');
             j++;
            }
       oi[i].y1=number;
    }
    
    int t=0;
    
    for ( int i = 1; i <= m; i++ )
    {  
       if ( BinaryS(oi[i].x1,oi[i].y1) == 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;
}