Cod sursa(job #46392)

Utilizator stef2nStefan Istrate stef2n Data 2 aprilie 2007 16:51:45
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.94 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(XRIGHT>P[mij].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;
}