Cod sursa(job #75663)

Utilizator sealTudose Vlad seal Data 4 august 2007 18:57:55
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
using namespace std;
#include<cstdio>
#include<algorithm>
#define Nm 50001
#define Cm 2000000001
int V[Nm],k,ans;
pair<int,int> C1[Nm],C2[Nm],C3[Nm],C4[Nm];

int bs(int v)
{
    if(V[k]>v)
        return ++k;

    int i=1,j=k,m;

    while(i<j)
    {
        m=i+j>>1;
        if(V[m]>v)
            i=m+1;
        else
            j=m;
    }
    return i;
}

void solve(pair<int,int> A[], int n)
{
    if(!n)
        return;

    int i;

    V[k=1]=A[0].second;
    for(i=1;i<n;++i)
        V[bs(A[i].second)]=A[i].second;
    ans+=k;
}

int main()
{
    int n,ox,oy,x,y,k1=0,k2=0,k3=0,k4=0;

    freopen("pachete.in","r",stdin);
    scanf("%d%d%d",&n,&ox,&oy);

    while(n--)
    {
        scanf("%d%d",&x,&y);
        if(x<ox)
            if(y<oy)
            {
                C1[k1].first=Cm-x;
                C1[k1++].second=Cm-y;
            }
            else
            {
                C2[k2].first=Cm-x;
                C2[k2++].second=y;
            }
        else
            if(y<oy)
            {
                C3[k3].first=x;
                C3[k3++].second=Cm-y;
            }
            else
            {
                C4[k4].first=x;
                C4[k4++].second=y;
            }
    }

    sort(C1,C1+k1);
    solve(C1,k1);
    sort(C2,C2+k2);
    solve(C2,k2);
    sort(C3,C3+k3);
    solve(C3,k3);
    sort(C4,C4+k4);
    solve(C4,k4);

    freopen("pachete.out","w",stdout);
    printf("%d\n",ans);

    return 0;
}