Cod sursa(job #2293028)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 30 noiembrie 2018 14:04:57
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <vector>

using namespace std;

#define lli long long int

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

static const int NMAX = 5e4+5;

int n;

lli dist[NMAX];
int sediuX, sediuY;
int distMax = -1;
int ns;
int ind[NMAX];
char s[25];

vector<pair<int,int> > v[5];

bool vizitat[NMAX];
inline int getnum()
{
    int x=0;
    while (s[ns]&&s[ns]!=' ')
        x=x*10+s[ns++]-'0';
    ns++;
    return x;
}

void ReadInput()
{
    fin >> n;
    fin >> sediuX >> sediuY;
    
    fin.get();
    int x,y;
    for(int i = 1; i<= n; ++i)
    {
        memset(s,0,sizeof(s));
        ns =0;
        fin.getline(s,25);

        x = getnum();
        y = getnum();

        x-=sediuX;
        y-=sediuY;

        if(x >0 && y > 0) v[1].push_back({x,y});
        if(x > 0 && y < 0) v[2].push_back({x,-y});
        if(x < 0 && y < 0) v[3].push_back({-x,-y});
        if(x < 0 && y > 0 ) v[4].push_back({-x,y});

    }
}

int Solve(vector<pair<int,int> > array)
{
    ind[0] = 0;
    int sz = 0;
    for(int i = 0; i< array.size(); ++i)
    {
        int x = array[i].first;
        int y = array[i].second;

        if(y > ind[sz])
            ind[++sz] = y;
        else
        {
            int left = 1, right = sz, mid, sol;
            while(left <= right)
            {
                mid = (left + right) >> 1;
                if(y <= ind[mid])
                {
                    sol = mid;
                    right = mid-1;
                }
                else
                    left = mid + 1;
            }
            ind[sol] = y;
        }
        
    }
    return sz;
}

int main()
{
    ReadInput();
    int sol = 0;
    for(int i =1 ; i<= 4; ++i)
    {
        sort(v[i].begin(), v[i].end());
        sol += Solve(v[i]);
    }
    fout << sol;
    return 0;
}