Cod sursa(job #1081152)

Utilizator monica11Szekely Monica monica11 Data 13 ianuarie 2014 11:32:24
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.49 kb
#include<fstream>
using namespace std;
ifstream f("pachete.in");
ofstream g("pachete.out");
struct pereche
{
    long x,y;
};
pereche x[50001],o,a;
long pos[10],b[50001],i,nr1,nr2,nr3,nr4,n,t1,t2,t3,t4,t;
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(x[i].x>x[j].x)
        {
            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(x[i].x<x[j].x)
        {
            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()
{
    f>>n;
    f>>o.x>>o.y;
    nr1=nr2=nr3=0;
    for(i=1;i<=n;i++)
    {
        f>>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++;
    }
    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;
    f>>n>>o.x>>o.y;
    for(i=1;i<=n;i++)
    {
        f>>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);
    qsort2(pos[3],pos[4]-1);
    qsort1(pos[4],pos[5]-1);
    long j;
    t1=0;
    b[0]=o.y;
    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]=o.y;
    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]=o.y;
    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]=o.y;
    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;
    g<<t;
    return 0;
}