Cod sursa(job #2353744)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 24 februarie 2019 15:55:19
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

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

vector < pair <int, int> > I, II, III, IV;
int N, Ox, Oy, x, y;

int Sol(vector < pair <int, int> > v)
{
    int N = v.end() - v.begin(), k = 0, dp[50005] = {0};
    sort(v.begin(), v.end());
    for (int i = 0; i < N; i++)
    {
        int st = 1, dr = k, mid, best = 0;
        while (st <= dr)
        {
            mid = (st + dr) / 2;
            if (dp[mid] < v[i].second)
            {
                best = mid;
                dr = mid - 1;
            }
            else
                st = mid + 1;
        }
        if (best == 0)
            dp[++k] = v[i].second;
        else
            dp[best] = v[i].second;
    }
    return k;
}

int main()
{
    fin >> N >> Ox >> Oy;
    while (N--)
    {
        fin >> x >> y;
        x -= Ox;
        y -= Oy;
        if (x > 0 && y > 0) I.push_back({x, y});
        else if (x < 0 && y > 0) II.push_back({-x, y});
        else if (x < 0 && y < 0) III.push_back({-x, -y});
        else if (x > 0 && y < 0) IV.push_back({x, -y});
    }
    fout << Sol(I) + Sol(II) + Sol(III) + Sol(IV);
    return 0;
}