Cod sursa(job #2098103)

Utilizator robx12lnLinca Robert robx12ln Data 2 ianuarie 2018 13:27:58
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include<fstream>
#include<deque>
#include<algorithm>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
int Ox, Oy, N, X, Y, sol;
vector< pair<int,int> > v[4];
deque<int> A;
inline int cadran( int X, int Y ){
    if( X >= 0 && Y >= 0 )
        return 0;
    if( X <= 0 && Y >= 0 )
        return 1;
    if( X <= 0 && Y <= 0 )
        return 2;
    if( X >= 0 && Y <= 0 )
        return 3;
}
void rotesc( int nr ){
    pair<int,int> P;
    if( nr == 1 ){
        for( int i = 0; i < v[nr].size(); i++ ){
            P = v[nr][i];
            v[nr][i].first = P.second;
            v[nr][i].second = -P.first;
        }
    }
    if( nr == 2 ){
        for( int i = 0; i < v[nr].size(); i++ ){
            P = v[nr][i];
            v[nr][i].first = -P.first;
            v[nr][i].second = -P.second;
        }
    }
    if( nr == 3 ){
        for( int i = 0; i < v[nr].size(); i++ ){
            P = v[nr][i];
            v[nr][i].first = -P.second;
            v[nr][i].second = P.first;
        }
    }
    return;
}
inline int solve( int nr ){
    if( v[nr].size() == 0 )
        return 0;
    sort( v[nr].begin(), v[nr].end() );
    A.clear();
    A.push_back( v[nr][0].second );
    for( int i = 1; i < v[nr].size(); i++ ){
        int F = A.front();
        if( v[nr][i].second < F ){
            A.push_front( v[nr][i].second );
        }else{
            int st, dr;
            st = 0;
            dr = A.size() - 1;
            while( st <= dr ){
                int mid = ( st + dr ) / 2;
                if( A[mid] <= v[nr][i].second )
                    st = mid + 1;
                else
                    dr = mid - 1;
            }
            A[dr] = v[nr][i].second;
        }
    }
    return (int)A.size();
}
int main(){
    fin >> N >> Ox >> Oy;
    for( int i = 1; i <= N; i++ ){
        fin >> X >> Y;
        X -= Ox; Y -= Oy;
        v[ cadran( X, Y ) ].push_back( make_pair( X, Y ) );
    }
    sol = 0;
    sol += solve( 0 );
    rotesc( 1 );
    sol += solve( 1 );
    rotesc( 2 );
    sol += solve( 2 );
    rotesc( 3 );
    sol += solve( 3 );
    fout << sol << "\n";
    return 0;
}