Cod sursa(job #2353769)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 24 februarie 2019 16:11:38
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>
#define lim (1 << 20)

using namespace std;

ofstream fout("pachete.out");

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

int pos;
char buff[lim];

int get(int &x)
{
    x = 0;
    while (!('0' <= buff[pos] && buff[pos] <= '9'))
    {
        if (++pos == lim)
        {

            fread(buff, 1, lim, stdin);
            pos = 0;
        }
    }
    while ('0' <= buff[pos] && buff[pos] <= '9')
    {
        x = x * 10 + buff[pos] - '0';
        if (++pos == lim)
        {
            fread(buff, 1, lim, stdin);
            pos = 0;
        }
    }
    return x;
}

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()
{
    freopen("pachete.in", "r", stdin);
    get(N);
    get(Ox);
    get(Oy);
    while (N--)
    {
        get(x);
        get(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;
}