Mai intai trebuie sa te autentifici.
Cod sursa(job #12934)
Utilizator | 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;
}