Cod sursa(job #2351442)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 22 februarie 2019 13:13:33
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <bits/stdc++.h>

#define Nmax 50005

using namespace std;

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

vector < pair <int, int> > I, II, III, IV;
int N;
int oX, oY;
int srt[Nmax];

int solve(vector < pair <int, int> > &V)
{
    for(auto &it : V)
        it.first = abs(it.first), it.second = abs(it.second);
    sort(V.begin(), V.end());
    int L = 0;
    for(auto it : V)
    {
        int pos = L + 1;
        for(int le = 1, ri = L; le <= ri;)
        {
            int mid = (le + ri) / 2;
            if(srt[L] <= it.second)
            {
                pos = mid;
                ri = mid - 1;
            }
            else
                le = mid + 1;
        }
        if(pos == L + 1)
            L++;
        srt[pos] = it.second;
    }
    return L;
}

int main()
{
    fin >> N >> oX >> oY;
    for(int i = 1; i <= N; i++)
    {
        int x, y;
        fin >> x >> y;
        x -= oX;
        y -= oY;
        if(x >= 0 && y >= 0)
            I.push_back({x, y});
        if(x < 0 && y >= 0)
            II.push_back({x, y});
        if(x < 0 && y < 0)
            III.push_back({x, y});
        if(x > 0 && y < 0)
            IV.push_back({x, y});
    }
    fout << solve(I) + solve(II) + solve(III) + solve(IV) << "\n";
    return 0;
}