Cod sursa(job #12914)

Utilizator moga_florianFlorian MOGA moga_florian Data 5 februarie 2007 11:51:49
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.24 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;    
}

void intersc(int i,int j)
{
int aux;
aux=xx[i];
xx[i]=xx[j];
xx[j]=aux;

aux=yy[i];
yy[i]=yy[j];
yy[j]=aux;     
}
     

int main()
{
FILE *fin=fopen("pachete.in","r"),
     *fout=fopen("pachete.out","w");
    
int n,i,j,k,li,lf,sol=0;
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];
  
   
for(i=1;i<=nn;i++)
  {
  j=i;
  while(j/2&&comp1(j/2,j)<0)
       {
       intersc(j/2,j);
       j/=2;
       }
  }
  
i=nn;
while(i>1)
 {
 intersc(1,i);
 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;
   
   intersc(j,k);
   j=k;      
   }         
 }
 
int mij;
m=0;
for(i=1;i<=nn;i++)
  {
  if(m==0||y[i]<ult[m])
     {
     m++;
     ult[m]=y[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]=y[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)
       {
       intersc(j/2,j);
       j/=2;
       }
  }
  
i=nn;
while(i>1)
 {
 intersc(1,i);
 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;
   
   intersc(j,k);
   j=k;      
   }         
 }
 
m=0;
for(i=1;i<=nn;i++)
  {
  if(m==0||y[i]<ult[m])
     {
     m++;
     ult[m]=y[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]=y[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)
       {
       intersc(j/2,j);
       j/=2;
       }
  }
  
i=nn;
while(i>1)
 {
 intersc(1,i);
 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;
   
   intersc(j,k);
   j=k;      
   }         
 }
 
m=0;
for(i=1;i<=nn;i++)
  {
  if(m==0||y[i]>ult[m])
     {
     m++;
     ult[m]=y[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]=y[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)
       {
       intersc(j/2,j);
       j/=2;
       }
  }
  
i=nn;
while(i>1)
 {
 intersc(1,i);
 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;
   
   intersc(j,k);
   j=k;      
   }         
 }
 
m=0;
for(i=1;i<=nn;i++)
  {
  if(m==0||y[i]<ult[m])
     {
     m++;
     ult[m]=y[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]=y[i];
  }
  }    
  
sol+=m;

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

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