Cod sursa(job #43470)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 30 martie 2007 09:32:32
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include<fstream>
#include<math.h>
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,t1max,t2max,t3max,t4max;


long  g(pereche a, pereche b)
{
if (fabs(a.x-O.x)+fabs(a.y-O.y)>fabs(b.x-O.x)+fabs(b.y-O.y)) return +1;
if (fabs(a.x-O.x)+fabs(a.y-O.y)<fabs(b.x-O.x)+fabs(b.y-O.y)) return -1;
return 0;
}

void selectare(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 (g(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 qsort(long p, long q)
{
long r;
if (p<q)
{
selectare(p,q,r);
qsort(p,r-1);
qsort(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;}
}

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


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

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

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

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

t=t1max+t2max+t3max+t4max;
fout<<t<<endl;
fin.close();
fout.close();
return 0;
}