Cod sursa(job #1517710)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 4 noiembrie 2015 18:40:20
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 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 );
}
pair< set< punct >::iterator, int > cb( punct a ) {
    pair< set< punct >::iterator, bool > i = s.insert( punct( a.x + 1, a.y ) );
    set< punct >::iterator it = i.first;
    if ( it == s.begin() ) {
        s.erase( i.first );
        return make_pair( s.begin(), -1 );
    } else {
        -- it;
        s.erase( i.first );
        return make_pair( it, 0 );
    }
}
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 ) {
            pair< set< punct >::iterator, int > it = cb( v[ k ][ i ] );
            if ( it.second != -1 ) {
                s.erase( it.first );
            }
            s.insert( v[ k ][ i ] );
        }
        ans += ( int )s.size();
    }
    fout << ans << "\n";
    fin.close();
    fout.close();
    return 0;
}