Cod sursa(job #164205)

Utilizator FlorinC1996Florin C FlorinC1996 Data 23 martie 2008 17:45:16
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.51 kb
#include <cstdio>   
#include <algorithm>   
using namespace std;   
  
#define infile "zoo.in"   
#define outfile "zoo.out"   
#define NMAX 16001   
#define INTERV_MAX 32770   
struct point {int x,y;};   
  
FILE *fin,*fout;   
int N;   
point P[NMAX];   
int cnt[INTERV_MAX];   
point *V[INTERV_MAX];   
int XLEFT,XRIGHT,YDOWN,YUP;   
  
inline int cmp(point p1, point p2)   
  {   
   return p1.x<p2.x;   
  }   
  
void interclasare(point *(&c), int an, point *a, int bn, point *b)   
  {   
   int i=0,j=0,ind=0;   
   while(i<an || j<bn)   
        {   
         while(i<an && j<bn && a[i].y<b[j].y)   
              c[ind++]=a[i++];   
         while(i<an && j<bn && a[i].y>b[j].y)   
              c[ind++]=b[j++];   
         while(i<an && j<bn && a[i].y==b[j].y)   
              {   
               c[ind++]=a[i++];   
               c[ind++]=b[j++];   
              }   
         while(i<an && j>=bn)   
              c[ind++]=a[i++];   
         while(j<bn && i>=an)   
              c[ind++]=b[j++];   
        }   
  }   
  
void build(int n, int li, int ls)   
  {   
   if(li==ls)   
     {   
      cnt[n]=1;   
      V[n]=new point[1];   
      V[n][0]=P[li];   
      return;   
     }   
   build(2*n,li,(li+ls)/2);   
   build(2*n+1,(li+ls)/2+1,ls);   
   cnt[n]=cnt[2*n]+cnt[2*n+1];   
   V[n]=new point[cnt[n]];   
   interclasare(V[n],cnt[2*n],V[2*n],cnt[2*n+1],V[2*n+1]);   
  }   
  
int binary_search1(point *V, int li, int ls) // pozitia primului punct de ordonata mai mare sau egala cu YDOWN   
  {   
   if(li>ls)   
     return -1;   
   if(li==ls)   
     if(YDOWN<=V[li].y)   
       return li;   
     else  
       return -1;   
   int mij=(li+ls)/2,aux;   
   if(YDOWN>V[mij].y)   
     return binary_search1(V,mij+1,ls);   
   else  
     {   
      aux=binary_search1(V,li,mij);   
      if(aux!=-1)   
        return aux;   
      else  
        return mij;   
     }   
  }   
  
int binary_search2(point *V, int li, int ls) // pozitia ultimului punct de ordonata mai mica sau egala cu YUP   
  {   
   if(li>ls)   
     return -1;   
   if(li==ls)   
     if(YUP>=V[li].y)   
       return li;   
     else  
       return -1;   
   int mij=(li+ls)/2,aux;   
   if(YUP<V[mij].y)   
     return binary_search2(V,li,mij-1);   
   else  
     {   
      aux=binary_search2(V,mij+1,ls);   
      if(aux!=-1)   
        return aux;   
      else  
        return mij;   
     }   
  }   
  
int query(int n, int li, int ls)   
  {   
   if(XLEFT>P[ls].x || XRIGHT<P[li].x)   
     return 0;   
   if(XLEFT<=P[li].x && P[ls].x<=XRIGHT)   
     {   
      int poz1,poz2;   
      poz1=binary_search1(V[n],0,cnt[n]-1);   
      poz2=binary_search2(V[n],0,cnt[n]-1);   
      if(poz1==-1 || poz2==-1 || poz1>poz2)   
        return 0;   
      return poz2-poz1+1;   
     }   
   int mij=(li+ls)/2,val=0;   
   if(XLEFT<=P[mij].x)   
     val+=query(2*n,li,mij);   
   if(mij+1<=ls && XRIGHT>=P[mij+1].x)   
     val+=query(2*n+1,mij+1,ls);   
   return val;   
  }   
  
  
int main()   
{   
int i,t;   
fin=fopen(infile,"r");   
fout=fopen(outfile,"w");   
fscanf(fin,"%d",&N);   
for(i=0;i<N;i++)   
   fscanf(fin,"%d %d",&P[i].x,&P[i].y);   
sort(P,P+N,cmp);   
build(1,0,N-1);   
fscanf(fin,"%d",&t);   
while(t)   
     {   
      fscanf(fin,"%d %d %d %d",&XLEFT,&YDOWN,&XRIGHT,&YUP);   
      fprintf(fout,"%d\n",query(1,0,N-1));   
      t--;   
     }   
fclose(fin);   
fclose(fout);   
return 0;   
}