Cod sursa(job #25294)

Utilizator stef2nStefan Istrate stef2n Data 4 martie 2007 11:50:40
Problema Ograzi Scor 40
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 3.05 kb
#include <stdio.h>
#include <stdlib.h>

#define infile "ograzi.in"
#define outfile "ograzi.out"
#define NMAX 50005
#define MMAX 100005
struct point {int x,y;};

FILE *fin,*fout;
int n,m,W,H;
point dr[NMAX];
point oi[MMAX];

void citire()
  {
   int i,j,number;
   char line[20];
   fin=fopen(infile,"r");
   fscanf(fin,"%d %d %d %d\n",&n,&m,&W,&H);
   for(i=0;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++;
            }
       dr[i].x=number;
       j++;
       number=0;
       while(line[j]>='0' && line[j]<='9')
            {
             number=number*10+(line[j]-'0');
             j++;
            }
       dr[i].y=number;
      }

   for(i=0;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].x=number;
       j++;
       number=0;
       while(line[j]>='0' && line[j]<='9')
            {
             number=number*10+(line[j]-'0');
             j++;
            }
       oi[i].y=number;
      }

   fclose(fin);
  }

inline int cmp(const void *va, const void *vb)
  {
   point a=*((point *)va);
   point b=*((point *)vb);
   return -(a.x<b.x)+(a.x>b.x);
  }

inline int cmp2(const void *va, const void *vb)
  {
   point a=*((point *)va);
   point b=*((point *)vb);
   if(a.x<b.x)
     return -1;
   if(a.x>b.x)
     return 1;
   if(a.y<b.y)
     return -1;
   if(a.y>b.y)
     return 1;
   return 0;
  }

int bs_min(point a, int li, int ls)
  {
   if(li>ls)
     return -1;
   if(li==ls)
     if((a.x-dr[li].x<=W) && (a.x-dr[li].x>=0))
       return li;
     else
       return -1;
   int mij=(li+ls)/2;
   if(a.x-dr[mij].x>W)
     return bs_min(a,mij+1,ls);
   if(a.x-dr[mij].x<0)
     return bs_min(a,li,mij-1);
   return bs_min(a,li,mij);
  }

int bs_max(point a, int li, int ls)
  {
   if(li>ls)
     return -1;
   if(li==ls)
     if((a.x-dr[li].x<=W) && (a.x-dr[li].x>=0))
       return li;
     else
       return -1;
   int mij=(li+ls)/2;
   if(a.x-dr[mij].x>W)
     return bs_max(a,mij+1,ls);
   if(a.x-dr[mij].x<0)
     return bs_max(a,li,mij-1);
   if(mij==li)
     {
      int aux=bs_max(a,mij+1,ls);
      if(aux==-1)
        return mij;
      else
        return aux;
     }
   return bs_max(a,mij,ls);
  }

inline int in_dr(point a, point dr)
  {
   return (a.x-dr.x>=0) && (a.x-dr.x<=W) && (a.y-dr.y>=0) && (a.y-dr.y<=H);
  }

int main()
{
int pozmin,pozmax,j;
citire();
qsort(dr,n,sizeof(point),cmp);
qsort(oi,m,sizeof(point),cmp2);
int count=0,lastcount=-1;
for(int i=0;i<m;i++)
   if(i && oi[i].x==oi[i-1].x && oi[i].y==oi[i-1].y)
     count+=lastcount;
   else
     {
      pozmin=bs_min(oi[i],0,n-1);
      pozmax=bs_max(oi[i],0,n-1);
      lastcount=0;
      if(pozmin!=-1)
        for(j=pozmin;(j<=pozmax)&&!lastcount;j++)
           lastcount=in_dr(oi[i],dr[j]);
      count+=lastcount;
     }
fout=fopen(outfile,"w");
fprintf(fout,"%d\n",count);
fclose(fout);
return 0;
}