Cod sursa(job #26348)

Utilizator quicksandMatei Tene quicksand Data 5 martie 2007 14:56:10
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <stdio.h>
#include <stdlib.h>

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

int 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;
}

int compara2 (long p[2],long d[2])
{ if (compara (p,d)<0) return -1;
  if (p[0]>=d[0] && p[0]<=d[0]+w && p[1]>=d[1] && p[1]<=d[1]+h) return 0;
  return 1;
}

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

  long i;
  for (i=0; i<n; i++)
      { fgets (lin,100,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)
{ long q=(p+r)/2;
  int c=compara2 (o,v[q]);
  if (c==0)
     return 1;
  if (p==r)
     return 0;

  if (c<0)
     return cauta (o,p,q);
  else
     return cauta (o,q+1,r);

}

void 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[100];
  for (i=0; i<m; i++)
      { fgets (lin,100,in);
        sscanf (lin,"%ld%ld",&(o[0]),&(o[1]));
        if (cauta (o,0,n-1))
           rez++;
      }
  fclose (in);

  tipar ();
  return 0;
}