Cod sursa(job #44646)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 31 martie 2007 16:53:53
Problema Pachete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
/*











*/
#include<fstream>
using namespace std;
fstream fin,fout;

struct pereche
{
long x,y;
};

pereche x[50001],O,a;

long pos[6],b[50001],i,nr1,nr2,nr3,nr4,N,t1,t2,t3,t4,t;

int f(pereche a, pereche b)
{
if (a.x<b.x) return -1;
if (a.x>b.x) return +1;
if (a.y<b.y) return -1;
if (a.y>b.y) return +1;
return 0;
}

void selectare1(long p, long q, long &r)
{
long i,j,di,dj;
pereche aux;
i=p; j=q; di=1; dj=0;
while (i<j)
{
if (f(x[i],x[j])>=0)
{
aux=x[i]; x[i]=x[j]; x[j]=aux;
di=1-di;
dj=1-dj;
}
i=i+di;
j=j-dj;
}
r=i;
}

void selectare2(long p, long q, long &r)
{
long i,j,di,dj;
pereche aux;
i=p; j=q; di=1; dj=0;
while (i<j)
{
if (f(x[i],x[j])<=0)
{
aux=x[i]; x[i]=x[j]; x[j]=aux;
di=1-di;
dj=1-dj;
}
i=i+di;
j=j-dj;
}
r=i;
}


void qsort1(long p, long q)
{
long r;
if (p<q)
{
selectare1(p,q,r);
qsort1(p,r-1);
qsort1(r+1,q);
}
}

void qsort2(long p, long q)
{
long r;
if (p<q)
{
selectare2(p,q,r);
qsort2(p,r-1);
qsort2(r+1,q);
}
}



int main(void)
{
fin.open("pachete.in",ios::in);
fout.open("pachete.out",ios::out);
fin>>N;
fin>>O.x>>O.y;
nr1=nr2=nr3=0;
for (i=1;i<=N;i++)
{
fin>>a.x>>a.y;
if ((a.x>O.x)&&(a.y>=O.y)) nr1++;//cadran I
  else if ((a.x<=O.x)&&(a.y>O.y)) nr2++; //cadran II
    else if ((a.x<O.x)&&(a.y<=O.y)) nr3++; //cadran III
    //restul in cadran IV
}
fin.close();
fin.open("pachete.in",ios::in);
pos[1]=1; pos[2]=nr1+1; pos[3]=pos[2]+nr2; pos[4]=pos[3]+nr3; pos[5]=N+1;
nr1=pos[1]-1; nr2=pos[2]-1; nr3=pos[3]-1; nr4=pos[4]-1;
fin>>N>>O.x>>O.y;
for (i=1;i<=N;i++)
{
fin>>a.x>>a.y;
if ((a.x>O.x)&&(a.y>=O.y)){nr1++;x[nr1]=a;}//cadran I
  else if ((a.x<=O.x)&&(a.y>O.y)) {nr2++;x[nr2]=a;}//cadran II
    else if ((a.x<O.x)&&(a.y<=O.y)) {nr3++;x[nr3]=a;} //cadran III
      else {nr4++;x[nr4]=a;} //cadran IV
}

qsort1(pos[1],pos[2]-1);
qsort2(pos[2],pos[3]-1);
qsort2(pos[3],pos[4]-1);
qsort1(pos[4],pos[5]-1);

long j;

t1=0;
b[0]=0;
for (i=pos[2]-1;i>=pos[1];i--)
	{
	j=t1; while (b[j]>x[i].y) j--;
        if (j==t1) { t1++; b[t1]=x[i].y;}
	   else b[j+1]=x[i].y;
	}
t2=0;
b[0]=0;
for (i=pos[3]-1;i>=pos[2];i--)
	{
	j=t2; while (b[j]>x[i].y) j--;
        if (j==t2) { t2++; b[t2]=x[i].y;}
	   else b[j+1]=x[i].y;
	}
t3=0;
b[0]=0;
for (i=pos[4]-1;i>=pos[3];i--)
	{
	j=t3; while (b[j]>x[i].y) j--;
        if (j==t3) { t3++; b[t3]=x[i].y;}
	   else b[j+1]=x[i].y;
	}
t4=0;
b[0]=0;
for (i=pos[5]-1;i>=pos[4];i--)
	{
	j=t4; while (b[j]>x[i].y) j--;
        if (j==t4) { t4++; b[t4]=x[i].y;}
	   else b[j+1]=x[i].y;
	}
t=t1+t2+t3+t4;
fout<<t<<endl;
fin.close();
fout.close();
return 0;
}