Cod sursa(job #1675788)

Utilizator borcanirobertBorcani Robert borcanirobert Data 5 aprilie 2016 16:14:31
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int MAXN = 50005;
struct Point{
    int x, y;
};
int N;
Point s, p;
vector<Point> P[4];
int D[4][MAXN];
int nrp[4];
int nd[4];

int BinarySearch( int k, int x );
bool Comp( const Point& x, const Point& y )
{
    if ( x.x < y.x || ( x.x == y.x && x.y < y.y ) )
        return true;
    return false;
}

int main()
{
    int i, j;
    int poz;

    fin >> N;
    fin >> s.x >> s.y;
  //  P[0].resize(N + 1);
  //  P[1].resize(N + 1);
 //   P[2].resize(N + 1);
   // P[3].resize(N + 1);

    for ( i = 1; i <= N; i++ )
    {
        fin >> p.x >> p.y;
        p.x -= s.x, p.y -= s.y;

        if ( p.x < 0 && p.y < 0 )
        {
            p.x = -p.x, p.y = -p.y;
            P[0].push_back( p );
            continue;
        }
        if ( p.x < 0 && p.y >= 0 )
        {
            p.x = -p.x;
            P[1].push_back( p );
            continue;
        }
        if ( p.x >= 0 && p.y < 0 )
        {
            p.y = -p.y;
            P[2].push_back( p );
            continue;
        }
        if ( p.x >= 0 && p.y >= 0 )
        {
            P[3].push_back( p );
            continue;
        }
    }

    for ( i = 0; i < 4; i++ )
        if ( P[i].size() > 0 )
        {
            nrp[i] = P[i].size();
            sort( P[i].begin(), P[i].end(), Comp );
            D[i][++nd[i]] = P[i][0].y;

            for ( j = 1; j < nrp[i]; j++ )
            {
                poz = BinarySearch(i, P[i][j].y);

                if ( D[i][poz] != 0 )
                    D[i][poz] = P[i][j].y;
                else
                    D[i][++nd[i]] = P[i][j].y;
            }
        }

    fout << nd[0] + nd[1] + nd[2] + nd[3] << '\n';

    fin.close();
    fout.close();
    return 0;
}

int BinarySearch( int k, int x )
{
    int st = 1, dr = nd[k], mid, rez = nd[k] + 1;

    while ( st <= dr )
    {
        mid = ( st + dr ) / 2;

        if ( D[k][mid] <= x )
        {
            rez = mid;
            dr = mid - 1;
        }
        else
            st = mid + 1;
    }

    return rez;
}