Cod sursa(job #38443)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 25 martie 2007 20:02:12
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include<fstream>
using namespace std;
fstream fin,fout;

struct pereche
{
long x,y;
};

pereche x[50001],O,a;

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

int f1(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;
}

int f2(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 (f1(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 (f2(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 selectare3(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 (f1(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 selectare4(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 (f2(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);
}
}

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

void qsort4(long p, long q)
{
long r;
if (p<q)
{
selectare4(p,q,r);
qsort4(p,r-1);
qsort4(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++;
  else if ((a.x<=O.x)&&(a.y>O.y)) nr2++;
    else if ((a.x<O.x)&&(a.y<=O.y)) nr3++;
}
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;}
  else if ((a.x<=O.x)&&(a.y>O.y)) {nr2++;x[nr2]=a;}
    else if ((a.x<O.x)&&(a.y<=O.y)) {nr3++;x[nr3]=a;}
      else {nr4++;x[nr4]=a;}
}

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

if (pos[2]-pos[1]>0) t1=1; else t1=0;
for (i=1+pos[1];i<pos[2];i++)
  if (x[i-1].y>x[i].y)t1++;

if (pos[3]-pos[2]>0) t2=1; else t2=0;
for (i=1+pos[2];i<pos[3];i++)
  if (x[i-1].y>x[i].y)t2++;

if (pos[4]-pos[3]>0) t3=1; else t3=0;
for (i=1+pos[3];i<pos[4];i++)
  if (x[i-1].y<x[i].y)t3++;

if (pos[5]-pos[4]>0) t4=1; else t4=0;
for (i=1+pos[4];i<pos[5];i++)
  if (x[i-1].y<x[i].y)t4++;

t=t1+t2+t3+t4;
fout<<t<<endl;
fin.close();
fout.close();
return 0;
}