Cod sursa(job #2312772)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 5 ianuarie 2019 15:02:41
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

struct str{int x, y;};

int N, x0, y0, x, y;

vector <str> C[5];

///C2 + C1
///---0+++
///C3 - C4

inline bool Comp(str a, str b) {
    return a.x > b.x;
}

int Solve(int k)
{
    sort(C[k].begin(), C[k].end(), Comp);

    vector <int> S; ///sortat crescator

    int st, dr, m, v, ans;

    if(C[k].size())
        S.push_back(C[k][0].y);

    for(int i = 1; i < (int)C[k].size(); i++)
    {
        st = 0, dr = S.size() - 1, v = C[k][i].y, ans = -1;

        while(st <= dr) {
            m = (st + dr) >> 1;

            if(v < S[m]) {
                ans = m;
                st = m + 1;
            } else
                dr = m - 1;
        }
        if(ans == -1)
            S.push_back(v);
        else
            S[ans] = v;
    }

    return S.size();
}

int main()
{
    fin >> N >> x0 >> y0;

    for(int i = 0; i < N; i++) {
        fin >> x >> y;

        x -= x0, y -= y0; ///reper 0,0

        if(x > 0 && y > 0)
            C[1].push_back({x, y});

        if(x < 0 && y > 0)
            C[2].push_back({-x, y});

        if(x < 0 && y < 0)
            C[3].push_back({-x, -y});

        if(x > 0 && y < 0)
            C[4].push_back({x, -y});
    }

    fout << Solve(1) + Solve(2) + Solve(3) + Solve(4) << '\n';

    fin.close();
    fout.close();

    return 0;
}