Cod sursa(job #1948341)

Utilizator RaduGiucleaGiuclea Radu RaduGiuclea Data 31 martie 2017 23:30:13
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <cstdio>
#include <algorithm>
using namespace std;
struct me{int x;int y;};
me c[5][50002];
int s[50002];
int cmp1(me a, me b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
int cmp2(me a,me b)
{
    return a.x>b.x||(a.x==b.x&&a.y<b.y);
}
int cmp3(me a,me b)
{
    return a.x>b.x||(a.x==b.x&&a.y>b.y);
}
int cmp4(me a,me b)
{

    return a.x<b.x||(a.x==b.x&&a.y>b.y);
}
int main()
{
    freopen("pachete.in","r",stdin);
    freopen("pachete.out","w",stdout);
    int n,i,ce1,ce2,x,y,k1=0,k2=0,k3=0,k4=0,u=0,st,dr,m,nr,pp,nrtot=0;
    scanf("%d%d%d",&n,&ce1,&ce2);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        x-=ce1;
        y-=ce2;
        if(x>=0&&y>=0)
            c[1][++k1].x=x,c[1][k1].y=y;
        if(x<0&&y>=0)
            c[2][++k2].x=x,c[2][k2].y=y;
        if(x<0&&y<0)
            c[3][++k3].x=x,c[3][k3].y=y;
        if(x>=0&&y<0)
            c[4][++k4].x=x,c[4][k4].y=y;
    }
    sort(&c[1][1],&c[1][k1+1],cmp1);
    sort(&c[2][1],&c[2][k2+1],cmp2);
    sort(&c[3][1],&c[3][k3+1],cmp3);
    sort(&c[4][1],&c[4][k4+1],cmp4);
    s[++u]=c[1][1].y;
    for(i=2;i<=k1;i++)
    {
        nr=c[1][i].y;
        if(nr<s[u])
            s[++u]=nr;
        else
        {
            st=1;
            dr=u;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(s[m]>=nr)
                    pp=m,st=m+1;
                else dr=m-1;
            }
            s[pp]=nr;
        }
    }
    if(k1)
        nrtot+=u;
    u=1;
    s[1]=c[2][1].y;
    for(i=2;i<=k2;i++)
    {
        nr=c[2][i].y;
        if(nr<s[u])
            s[++u]=nr;
        else
        {
            st=1;
            dr=u;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(s[m]>=nr)
                    pp=m,st=m+1;
                else dr=m-1;
            }
            s[pp]=nr;
        }
    }
    if(k2)
        nrtot+=u;
    u=1;
    s[1]=c[3][1].y;
    for(i=2;i<=k3;i++)
    {
        nr=c[3][i].y;
        if(nr>s[u])
            s[++u]=nr;
        else
        {
            st=1;
            dr=u;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(s[m]<nr)
                    st=m+1;
                else dr=m-1,pp=m;
            }
            s[pp]=nr;
        }
    }
    if(k3)
        nrtot+=u;
    u=1;
    s[1]=c[4][1].y;
    for(i=2;i<=k4;i++)
    {
        nr=c[4][i].y;
        if(nr>s[u])
            s[++u]=nr;
        else
        {
            st=1;
            dr=u;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(s[m]<nr)
                    st=m+1;
                else dr=m-1,pp=m;
            }
            s[pp]=nr;
        }
    }
    if(k4)
        nrtot+=u;
    printf("%d",nrtot);
    return 0;
}