Cod sursa(job #1517687)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 4 noiembrie 2015 18:16:39
Problema Pachete Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

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

const int nmax = 5 * 1e4;

struct punct{
    int x, y;

    punct() {}
    punct( int xx, int yy ) : x( xx ), y( yy ) {}

    inline bool operator < ( const punct &a ) const {
        if ( y != a.y ) {
            return ( y < a.y );
        }
        return ( x < a.x );
    }
};
vector< punct > v[ 4 ];
set< punct > s;

bool cmp( punct a, punct b ) {
    if ( a.x != b.x ) {
        return ( a.x < b.x );
    }
    return ( a.y < b.y );
}
int main() {
    int n, xx, yy;
    fin >> n >> xx >> yy;
    for( int i = 0; i < n; ++ i ) {
        int x, y;
        fin >> x >> y;
        x -= xx; y -= yy;
        if ( x >= 0 && y >= 0 ) {
            v[ 0 ].push_back( punct( x, y ) );
        } else if ( x < 0 && y >= 0 ) {
            v[ 3 ].push_back( punct( -x, y ) );
        } else if ( x < 0 && y < 0 ) {
            v[ 2 ].push_back( punct( -x, -y ) );
        } else {
            v[ 1 ].push_back( punct( x, -y ) );
        }
    }
    int ans = 0;
    for( int k = 0; k < 4; ++ k ) {
        sort( v[ k ].begin(), v[ k ].end(), cmp );
        s.clear();
        for( int i = 0; i < ( int )v[ k ].size(); ++ i ) {
            set< punct >::iterator it = upper_bound( s.begin(), s.end(), v[ k ][ i ] );
            if ( it != s.begin() ) {
                -- it;
                s.erase( it );
            }
            s.insert( v[ k ][ i ]);
        }
        ans += ( int )s.size();
    }
    fout << ans << "\n";
    fin.close();
    fout.close();
    return 0;
}