Cod sursa(job #7079)

Utilizator mariusdrgdragus marius mariusdrg Data 21 ianuarie 2007 12:22:21
Problema Pachete Scor 50
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 2.25 kb
#include<stdio.h>
#include<algorithm>


using namespace std;


const int maxn = 50001;



long long x[maxn];
long long y[maxn];
long long l;
long long ul;
long long i;
long long dr;
long long st[maxn];
long long xf,yf;
long long n;

long long modul(long long a)
{
        if (a<0)  return (-1)*a;
        return a;
}

bool cmpf(const int &a,const int &b)
{
        return modul(x[a])<modul(x[b]);
}

bool comp(long long a,long long b)
{
        return (modul(x[a])<=modul(x[b])&&modul(y[a])<=modul(y[b]));
}


void inf()
{
        long long fol=0;
        long long ul=0;
        sort(st+1,st+l+1,cmpf);
        while(fol<l)
        {
                for(i=1;i<=l;i++)
                {
                        if (st[i]!=-1&&comp(ul,st[i]))
                        {
                                ul=st[i];
                                st[i]=-1;
                                fol++;
                        }
                }
                dr++;
                ul=0;
        }
}



int main()
{
        freopen("pachete.in","r",stdin);
        freopen("pachete.out","w",stdout);
        scanf("%d",&n);
        scanf("%lld %lld",&xf,&yf);
        for(i=1;i<=n;i++)
        {
                scanf("%lld %lld",&x[i],&y[i]);
                x[i]-=xf;
                y[i]-=yf;

        }
        l=0;
        for(i=1;i<=n;i++)
        {
                if (x[i]<=0&&y[i]<=0)
                {
                        l++;
                        st[l]=i;
                }
        }
        inf();
        l=0;
        for(i=1;i<=n;i++)
        {
                if (x[i]>=0&&y[i]<=0)
                {
                        l++;
                        st[l]=i;
                }
        }
        inf();
        l=0;
        for(i=1;i<=n;i++)
        {
                if (x[i]>=0&&y[i]>=0)
                {
                        l++;
                        st[l]=i;
                }
        }
        inf();
        l=0;
        for(i=1;i<=n;i++)
        {
                if (x[i]<=0&&y[i]>=0)
                {
                        l++;
                        st[l]=i;
                }
        }
        inf();
        printf("%lld\n",dr);
        return 0;


}