Cod sursa(job #295405)

Utilizator alecmanAchim Ioan Alexandru alecman Data 3 aprilie 2009 11:42:44
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

#define INPUT "ograzi.in"
#define OUTPUT "ograzi.out"

const int SMAX = 20;
const long NMAX = 50001;

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

char Sir[ SMAX ];
long N, M, W, H;
long DrX[ NMAX ], DrY[ NMAX ], Poz[ NMAX ];

void readData()
{
  int cont = 0;
  long X, Y;
  char C;
	
  fscanf(fin, "%ld %ld %ld %ld", &N, &M, &W, &H);
  
  for(long i = 1; i <= N; ++i)
  {
    /*fgets(Sir, SMAX, fin);
    
    cont = 0;
    X = Y = 0;
    
    while(Sir[ cont ] != ' ') X = X*10 + (Sir[ cont ] - '0'), ++cont;
    
    ++cont;
    
    while(Sir[ cont ] != '\n' && Sir[ cont ] != '\0') Y = Y*10 + (Sir[ cont ] - '0'), ++cont;*/
    
    fscanf(fin, "%ld %ld", &X, &Y);
    
    DrX[ i ] = X;
    DrY[ i ] = Y;
    Poz[ i ] = i;
  }
}

inline int cmp(long A, long B)
{
  if(DrX[ A ] == DrX[ B ]) return DrY[ A ] < DrY[ B ];
  return DrX[ A ] < DrX[ B ];
}

int binSrch(long Left, long Right, long VX, long VY)
{
  if(Left > Right) return 0;
  
  long mid = (Left + Right) >> 1;
  int caz = 0;
  
    //fprintf(stderr, "Left=%ld Right=%ld mid=%ld\n", Left, Right, mid);
  
  if(DrX[ Poz[ mid ] ] <= VX && (DrX[ Poz[ mid ] ] + W >= VX) && DrY[ Poz[ mid ] ] <= VY && (DrY[ Poz[ mid ] ] + H >= VY)) return 1;
  else
  if(DrX[ Poz[ mid ] ] <= VX && (DrX[ Poz[ mid ] ] + W >= VX))
  {
    if(DrY[ Poz[ mid ] ] > VY) caz = 1;
    else caz = 2;
  }
  else
  if(DrX[ Poz[ mid ] ] > VX) caz = 1;
  else caz = 2;
  
  if(caz == 1) return binSrch(Left, mid-1, VX, VY);
  else return binSrch(mid+1, Right, VX, VY);
}

void solve()
{
  long X, Y;
  long Final = 0;
	
  for(long i = 1; i <= M; ++i)
  {
  	fscanf(fin, "%ld %ld", &X, &Y);
  	
  	Final += binSrch(1, N, X, Y);
  	
  	//fprintf(stderr, "%ld\n", Final);
  }
  
  fprintf(fout, "%ld\n", Final);
}

int main()
{
  readData();
  
  sort(Poz+1, Poz+N+1, cmp);
  
  /*for(long i = 1; i <= N; ++i)
  fprintf(stderr, "X=%ld Y=%ld\n", DrX[ Poz[ i ] ], DrY[ Poz[ i ] ]);*/
  
  solve();
	
  fclose(fin);
  fclose(fout);
  
  return 0;
}