Cod sursa(job #38001)

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

struct pereche
{
unsigned int x,y;
};

pereche x[50001],O,a;

unsigned p[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(unsigned p, unsigned q, unsigned &r)
{
unsigned int 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(unsigned p, unsigned q, unsigned &r)
{
unsigned int 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(unsigned p, unsigned q, unsigned &r)
{
unsigned int 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(unsigned p, unsigned q, unsigned &r)
{
unsigned int 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(unsigned p, unsigned q)
{
unsigned r;
if (p<q)
{
selectare1(p,q,r);
qsort1(p,r-1);
qsort1(r+1,q);
}
}

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

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

void qsort4(unsigned p, unsigned q)
{
unsigned 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;
n1=n2=n3=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);
p[1]=1; p[2]=nr1+1; p[3]=p[2]+nr2; p[4]=p[3]+nr3; p[5]=N+1;
nr1=p[1]-1; nr2=p[2]-1; nr3=p[3]-1; nr4=p[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(p[1],p[2]-1);
qsort2(p[2],p[3]-1);
qsort3(p[3],p[4]-1);
qsort4(p[4],p[5]-1);

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

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

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

if (p[5]-p[4]>0) t4=1; else t4=0;
for (i=1+p[4];i<p[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;
}