Cod sursa(job #28339)

Utilizator ionescu_bogdanIonescu Bogdan-Gabriel ionescu_bogdan Data 7 martie 2007 18:57:59
Problema Pachete Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define nmax 50010

int n,px,py,x[nmax],y[nmax],i,j,xx[nmax],yy[nmax],ord[nmax];
int s[nmax],ss,nn,sol;

int fc(const void *a,const void *b)
{
    if (xx[*(int*)a]!=xx[*(int*)b])
        return xx[*(int*)a]-xx[*(int*)b];
    return yy[*(int*)a]-yy[*(int*)b];
}

void solve()
{
    memset(s,0,sizeof(s)),ss=0;
    for (i=0;i<nn;i++)
        ord[i]=i;
    qsort((void*)ord,nn,sizeof(ord[0]),fc);
    for (i=0;i<nn;i++)
    {
        j=0;
        while (s[j]>yy[ord[i]])
            ++j;
        if (ss==j)
            ++ss;
        s[j]=yy[ord[i]];
    }
    sol+=ss;
}

int main()
{
    freopen("pachete.in","r",stdin);
    freopen("pachete.out","w",stdout);

    scanf("%d%d%d",&n,&px,&py);
    for (i=0;i<n;i++)
        scanf("%d%d",x+i,y+i);
    nn=0;
    for (i=0;i<n;i++)
        if ((x[i]>=px)&&(y[i]>=py))
            xx[nn]=x[i]-px,yy[nn]=y[i]-py,++nn;
    solve();
    nn=0;
    for (i=0;i<n;i++)
        if ((x[i]>=px)&&(y[i]<py))
            xx[nn]=x[i]-px,yy[nn]=py-y[i],++nn;
    solve();
    nn=0;
    for (i=0;i<n;i++)
        if ((x[i]<px)&&(y[i]>=py))
            xx[nn]=px-x[i],yy[nn]=y[i]-py,++nn;
    solve();
    nn=0;
    for (i=0;i<n;i++)
        if ((x[i]<px)&&(y[i]<py))
            xx[nn]=px-x[i],yy[nn]=py-y[i],++nn;
    solve();
    printf("%d\n",sol);
        
    return 0;
}