Cod sursa(job #1158845)

Utilizator PatrikStepan Patrik Patrik Data 29 martie 2014 09:51:54
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    #define NMAX 50001
    #define LL long long
    int N , Xs , Ys , cnt[5] , h[NMAX] ,rez;
    struct punct
    {
        LL x,y;
    }P[5][NMAX];
    bool f(punct A , punct B)
    {
        if(A.x == B.x)return A.y < B.y;
        return A.x < B.x;
    }

    void read();
    void solve(int n);
    void write();
    void cauta(int n , int val);

    int main()
    {
        read();
        for(int i = 1 ; i <= 4 ; ++i )
            if(cnt[i])
            solve(i);
        write();
        return 0;
    }

    void read()
    {
        int x , y;
        freopen("pachete.in" , "r" , stdin );
        scanf("%d%d%d" , &N , &Xs , &Ys);
        for(int i = 1 ; i<= N ; ++i )
        {
            scanf("%d%d" , &x , &y );
            x-=Xs ; y-=Ys;
            if(x >= 0)
                if(y >= 0) P[1][++cnt[1]].x = x,P[1][cnt[1]].y = y;
                else P[4][++cnt[4]].x = x, P[4][cnt[4]].y = -y;
            else
                if(y >= 0) P[2][++cnt[2]].x = -x, P[2][cnt[2]].y = y;
                else P[3][++cnt[3]].x = -x, P[3][cnt[3]].y = -y;
        }
    }

    void solve(int n)
    {
        sort(P[n]+1,P[n]+cnt[n]+1,f);
        for(int i = 1 ; i<= cnt[n] ; ++i )h[i] = 0;
        int k = 1;
        h[1] = P[n][1].y;
        for(int i = 2 ; i <= cnt[n] ; ++i )
            if(h[k] > P[n][i].y)
                h[++k] = P[n][i].y;
            else cauta(k,P[n][i].y);
        rez += k;
    }

    void cauta(int n , int val)
    {
        int ls = 1 , ld = n , mid , poz;
        while(ls <= ld )
        {
            mid = (ls+ld)/2;
            if(h[mid] <= val)
            {
                poz =mid;
                ld = mid-1;
            }
            else ls = mid+1;
        }
        h[poz] = val;
    }

    void write()
    {
        freopen("pachete.out" , "w" , stdout );
        printf("%d" , rez);
    }