Cod sursa(job #1917397)

Utilizator razvandraghiciDraghici Razvan razvandraghici Data 9 martie 2017 12:10:16
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("pachete.in");
ofstream fout("pachete.out");

int n, i, j, k1, k2, k3, k4, v[50003], st, dr, mid, X, Y, x, y, nr, sol;

pair <int, int> a[50003];

pair <int, int> b[50003];

pair <int, int> c[50003];

pair <int, int> d[50003];

int main()
{
    fin>>n;
    fin>>X>>Y;
    for(i=1;i<=n;i++){
        fin>>x>>y;
        x-=X;
        y-=Y;
        if(x>0){
            if(y>0)
                a[++k1].first=x,a[k1].second=y;
            else
                d[++k4].first=x,d[k4].second=y;
        }
        else{
            if(y>0)
                b[++k2].first=x,b[k2].second=y;
            else
                c[++k3].first=x,c[k3].second=y;
        }
    }

    sort(a+1, a+k1+1);


    for(i=1;i<=k1;i++){
        if(v[++nr]>a[i].second || nr==0)
            v[nr]=a[i].second;
        else{
            st=1;
            dr=nr;
            while(st<=dr){
                mid=(st+dr)/2;
                if(v[mid]<a[i].second)
                    dr=mid-1;
                else
                    st=mid+1;
            }
            v[st]=a[i].second;
        }
    }

    sol+=nr;

    for(i=1;i<=k2;i++)
        b[i].first=-b[i].first;

    nr=0;

    sort(b+1, b+k2+1);


    for(i=1;i<=k2;i++){
        if(v[++nr]>b[i].second || nr==0 )
            v[nr]=b[i].second;
        else{
            st=1;
            dr=nr;
            while(st<=dr){
                mid=(st+dr)/2;
                if(v[mid]<b[i].second)
                    dr=mid-1;
                else
                    st=mid+1;
            }
            v[st]=b[i].second;
        }
    }

    sol+=nr;

    nr=0;

    for(i=1;i<=k3;i++){
        c[i].first=-c[i].first;
        c[i].second=-c[i].second;
    }

    sort(c+1, c+k3+1);


    for(i=1;i<=k1;i++){
        if(v[++nr]>c[i].second || nr==0)
            v[nr]=c[i].second;
        else{
            st=1;
            dr=nr;
            while(st<=dr){
                mid=(st+dr)/2;
                if(v[mid]<c[i].second)
                    dr=mid-1;
                else
                    st=mid+1;
            }
            v[st]=c[i].second;
        }
    }

    sol+=nr;

    nr=0;

    for(i=1;i<=k4;i++)
        d[i].second=-d[i].second;

    sort(d+1, d+k4+1);


    for(i=1;i<=k1;i++){
        if(v[++nr]>d[i].second || nr==0)
            v[nr]=d[i].second;
        else{
            st=1;
            dr=nr;
            while(st<=dr){
                mid=(st+dr)/2;
                if(v[mid]<d[i].second)
                    dr=mid-1;
                else
                    st=mid+1;
            }
            v[st]=d[i].second;
        }
    }

    sol+=nr;

    fout<<sol;

    return 0;
}