Cod sursa(job #26383)

Utilizator quicksandMatei Tene quicksand Data 5 martie 2007 15:29:40
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <stdio.h>
#include <stdlib.h>

long v[50000][2],n,m,w,h,rez=0;
FILE* in=fopen ("ograzi.in","r");

int inline compara (const void* a,const void* b)
{ long *x=(long*)a, *y=(long*)b;

  if (x[0]<y[0] || (x[0]==y[0] && x[1]<y[1])) return -1;
  if (x[0]==y[0] && x[1]==y[1]) return 0;
  return 1;
}

void inline citeste ()
{ char *lin=new char[25];
  fgets (lin,25,in);
  sscanf (lin,"%ld%ld%ld%ld",&n,&m,&w,&h);

  long i;
  for (i=0; i<n; i++)
      { fgets (lin,25,in);
        sscanf (lin,"%ld%ld",&(v[i][0]),&(v[i][1]));
      }
  qsort (v,n,2*sizeof(long),compara);
}

int cauta (long o[2],long p,long r)
{ if (p>=r)
     return 0;

  long q=(p+r)/2;

  if (o[0]>=v[q][0] && o[0]<=v[q][0]+w && o[1]>=v[q][1] && o[1]<=v[q][1]+h)
     return 1;

  if (o[0]<v[q][0] || (o[0]==v[q][0] && o[1]<v[q][1]))
     return cauta (o,p,q);
  else
     return cauta (o,q+1,r);

}

void inline tipar ()
{ FILE* out=fopen ("ograzi.out","w");
  fprintf (out,"%ld\n",rez);
  fclose (out);
}

int main ()
{ citeste ();

  long i,o[2];
  char *lin=new char[25];
  for (i=1; i<=m; i++)
      { fgets (lin,25,in);
        sscanf (lin,"%ld%ld",&(o[0]),&(o[1]));
        if (cauta (o,0,n-1))
           rez++;
      }
  fclose (in);

  tipar ();
  return 0;
}