Mai intai trebuie sa te autentifici.

Cod sursa(job #12934)

Utilizator moga_florianFlorian MOGA moga_florian Data 5 februarie 2007 12:20:25
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.63 kb
#include<stdio.h>

int xi,yi,x[50005],y[50005],xx[50005],yy[50005],nn;
int ult[50005],m;

int comp1(int i,int j)
{
if(xx[i]<xx[j])
   return -1;
if(xx[i]>xx[j])
   return 1;
if(yy[i]<yy[j])
   return -1;
return 1;    
}

int comp2(int i,int j)
{
if(xx[i]<xx[j])
  return 1;
if(xx[i]>xx[j])
   return -1;
if(yy[i]<yy[j])
   return -1;
return 1;    
}

int comp3(int i,int j)
{
if(xx[i]<xx[j])
  return 1;
if(xx[i]>xx[j])
  return -1;
if(yy[i]<yy[j])
   return 1;
return -1;   
}

int comp4(int i,int j)
{
if(xx[i]<xx[j])
   return -1;
if(xx[i]>xx[j])
   return 1;
if(yy[i]<yy[j])
   return 1;
return -1;    
}

int main()
{
FILE *fin=fopen("pachete.in","r"),
     *fout=fopen("pachete.out","w");
    
int n,i,j,k,li,lf,sol=0,aux,ii,jj;
fscanf(fin,"%d%d%d",&n,&xi,&yi);
for(i=1;i<=n;i++)
   fscanf(fin,"%d%d",&x[i],&y[i]);

//primu cadran
nn=0;
for(i=1;i<=n;i++)
   if(x[i]>=xi&&y[i]>=yi)
      xx[++nn]=x[i],yy[nn]=y[i];
  
return 0;
for(i=1;i<=nn;i++)
  {
  j=i;
  while(j/2&&comp1(j/2,j)<0)
       {
       ii=j;
       jj=j/2;
                            
       aux=xx[ii];
       xx[ii]=xx[jj];
       xx[jj]=aux;

       aux=yy[ii];
       yy[ii]=yy[jj];
       yy[jj]=aux;     

       j/=2;
       }
  }
  
i=nn;
while(i>1)
 {
 ii=1;
 jj=i;
 aux=xx[ii];
 xx[ii]=xx[jj];
 xx[jj]=aux;

 aux=yy[ii];
 yy[ii]=yy[jj];
 yy[jj]=aux;     

 i--;
 
 j=1;
 while(1)
   {
   k=2*j;
   if(k>i) break;
   if(k+1<=i&&comp1(k+1,k)>0) k++;
   if(comp1(j,k)>0) break;

   ii=j;
   jj=k;
   aux=xx[ii];
   xx[ii]=xx[jj];
   xx[jj]=aux;

   aux=yy[ii];
   yy[ii]=yy[jj];
   yy[jj]=aux;     
   
   j=k;      
   }         
 }
 
int mij;
m=0;
for(i=1;i<=nn;i++)
  {
  if(m==0||yy[i]<ult[m])
     {
     m++;
     ult[m]=yy[i];            
     }
  else
  {                  
  li=1;lf=m;
  while(lf-li>0)
    {
    mij=(li+lf)/2;
    if(ult[mij]<=yy[i])
        lf=mij;              
    else
        li=mij;
    } 
    
  ult[m]=yy[i];
  }
  }    
  
sol+=m;

//cadranu 2
nn=0;
for(i=1;i<=n;i++)
   if(x[i]<xi&&y[i]>=yi)
      xx[++nn]=x[i],yy[nn]=y[i];
  
   
for(i=1;i<=nn;i++)
  {
  j=i;
  while(j/2&&comp2(j/2,j)<0)
       {
       ii=j;
       jj=j/2;
                            
       aux=xx[ii];
       xx[ii]=xx[jj];
       xx[jj]=aux;

       aux=yy[ii];
       yy[ii]=yy[jj];
       yy[jj]=aux;     

       j/=2;
       }
  }
  
i=nn;
while(i>1)
 {
 ii=1;
 jj=i;
 aux=xx[ii];
 xx[ii]=xx[jj];
 xx[jj]=aux;

 aux=yy[ii];
 yy[ii]=yy[jj];
 yy[jj]=aux;     
 i--;
 
 j=1;
 while(1)
   {
   k=2*j;
   if(k>i) break;
   if(k+1<=i&&comp2(k+1,k)>0) k++;
   if(comp2(j,k)>0) break;
   
   ii=j;
   jj=k;
   aux=xx[ii];
   xx[ii]=xx[jj];
   xx[jj]=aux;

   aux=yy[ii];
   yy[ii]=yy[jj];
   yy[jj]=aux;     
   j=k;      
   }         
 }
 
m=0;
for(i=1;i<=nn;i++)
  {
  if(m==0||yy[i]<ult[m])
     {
     m++;
     ult[m]=yy[i];            
     }
  else
  {                  
  li=1;lf=m;
  while(lf-li>0)
    {
    mij=(li+lf)/2;
    if(ult[mij]<=yy[i])
        lf=mij;              
    else
        li=mij;
    } 
    
  ult[m]=yy[i];
  }
  }    
  
sol+=m;

//cadranu 3
nn=0;
for(i=1;i<=n;i++)
   if(x[i]<xi&&y[i]<yi)
      xx[++nn]=x[i],yy[nn]=y[i];
  
   
for(i=1;i<=nn;i++)
  {
  j=i;
  while(j/2&&comp3(j/2,j)<0)
       {
       ii=j;
       jj=j/2;
                            
       aux=xx[ii];
       xx[ii]=xx[jj];
       xx[jj]=aux;

       aux=yy[ii];
       yy[ii]=yy[jj];
       yy[jj]=aux;     

       j/=2;
       }
  }
  
i=nn;
while(i>1)
 {
 ii=1;
 jj=i;
 aux=xx[ii];
 xx[ii]=xx[jj];
 xx[jj]=aux;

 aux=yy[ii];
 yy[ii]=yy[jj];
 yy[jj]=aux;     
 i--;
 
 j=1;
 while(1)
   {
   k=2*j;
   if(k>i) break;
   if(k+1<=i&&comp3(k+1,k)>0) k++;
   if(comp3(j,k)>0) break;
   
   ii=j;
   jj=k;
   aux=xx[ii];
   xx[ii]=xx[jj];
   xx[jj]=aux;

   aux=yy[ii];
   yy[ii]=yy[jj];
   yy[jj]=aux;     
   j=k;      
   }         
 }
 
m=0;
for(i=1;i<=nn;i++)
  {
  if(m==0||yy[i]>ult[m])
     {
     m++;
     ult[m]=yy[i];            
     }
  else
  {                  
  li=1;lf=m;
  while(lf-li>0)
    {
    mij=(li+lf)/2;
    if(ult[mij]>=y[i])
        lf=mij;              
    else
        li=mij;
    } 
    
  ult[m]=yy[i];
  }
  }    
  
sol+=m;

//cadranu 4
nn=0;
for(i=1;i<=n;i++)
   if(x[i]>=xi&&y[i]<yi)
      xx[++nn]=x[i],yy[nn]=y[i];
  
   
for(i=1;i<=nn;i++)
  {
  j=i;
  while(j/2&&comp4(j/2,j)<0)
       {
       ii=j;
       jj=j/2;
                            
       aux=xx[ii];
       xx[ii]=xx[jj];
       xx[jj]=aux;

       aux=yy[ii];
       yy[ii]=yy[jj];
       yy[jj]=aux;     

       j/=2;
       }
  }
  
i=nn;
while(i>1)
 {
 ii=1;
 jj=i;
 aux=xx[ii];
 xx[ii]=xx[jj];
 xx[jj]=aux;

 aux=yy[ii];
 yy[ii]=yy[jj];
 yy[jj]=aux;     
 i--;
 
 j=1;
 while(1)
   {
   k=2*j;
   if(k>i) break;
   if(k+1<=i&&comp4(k+1,k)>0) k++;
   if(comp4(j,k)>0) break;
   
   ii=j;
   jj=k;
   aux=xx[ii];
   xx[ii]=xx[jj];
   xx[jj]=aux;

   aux=yy[ii];
   yy[ii]=yy[jj];
   yy[jj]=aux;     
   j=k;      
   }         
 }
 
m=0;
for(i=1;i<=nn;i++)
  {
  if(m==0||yy[i]<ult[m])
     {
     m++;
     ult[m]=yy[i];            
     }
  else
  {                  
  li=1;lf=m;
  while(lf-li>0)
    {
    mij=(li+lf)/2;
    if(ult[mij]>=yy[i])
        lf=mij;              
    else
        li=mij;
    } 
    
  ult[m]=yy[i];
  }
  }    
  
sol+=m;

//afish
fprintf(fout,"%d\n",sol);

fclose(fin);
fclose(fout);
return 0;    
}