Cod sursa(job #2293132)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 30 noiembrie 2018 16:25:42
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 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;
int sediuX, sediuY;
int ns;
int ind[NMAX];
char s[25];

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

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)
{
    memset(ind,0,sizeof(ind));
    int sz = 0;

    for(int i = 0; i< array.size(); ++i)
    {
        int left = 1, right = sz, mid, sol = 1;

        while(left<= right)
        {
            int mid = (left + right) >> 1;
            if(ind[mid] <= array[i].second)
            {
                sol = 0;
                right = mid - 1;
            }
            else
                left = mid + 1;
        }
        if(sol)
            ind[++sz] = array[i].second;
        else
            ind[left] = array[i].second;
        
    }
    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;
}