Cod sursa(job #1756722)

Utilizator Athena99Anghel Anca Athena99 Data 13 septembrie 2016 15:34:16
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

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

const int nmax= 50000;

struct str {
    int x, y;
};

int z[nmax+1];

vector <str> v[nmax+1];

inline str mp( int x, int y ) {
    str sol;
    sol.x= x, sol.y= y;

    return sol;
}

bool cmp( str x, str y ) {
    return x.x<y.x;
}

int main(  ) {
    int n, x, y;
    fin>>n>>x>>y;
    for ( int i= 1; i<=n; ++i ) {
        int a, b;
        fin>>a>>b;
        if ( a>x && b>y ) {
            v[0].push_back(mp(a-x, b-y));
        } else if ( a>x ) {
            v[1].push_back(mp(a-x, y-b));
        } else if ( a<x && b>y ) {
            v[2].push_back(mp(x-a, b-y));
        } else {
            v[3].push_back(mp(x-a, y-b));
        }
    }

    int sol= 0;
    for ( int cnt= 0; cnt<4; ++cnt ) {
        sort( v[cnt].begin(), v[cnt].end(), cmp );

        int k= 0;
        for ( vector <str>::iterator it= v[cnt].begin(); it!=v[cnt].end(); ++it ) {
            int l, r, aux= 1;
            for ( l= 1, r= k; l<=r && aux==1; ) {
                if ( z[(l+r)/2]>(*it).y ) {
                    l= (l+r)/2+1;
                } else {
                    aux= 0;
                    r= (l+r)/2-1;
                }
            }

            int nr= l;
            if ( aux==1 ) {
                nr= ++k;
            }
            z[nr]= (*it).y;
        }
        sol+= k;
    }

    fout<<sol<<"\n";

    return 0;
}