Cod sursa(job #2716806)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 5 martie 2021 18:17:57
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>
#define int long long
#define pi pair<int,int>
#define x first
#define y second

using namespace std;

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

int N, ans;
pi p;
vector<pi> cadran[4];

int solve(int index) {
    N = cadran[index].size();
    sort(cadran[index].begin(), cadran[index].end());
    vector<int> sol{0};
    for(int i = 0; i < N; ++i) {
        int st = 1, dr = sol.size() - 1, poz = 0;
        while(st <= dr) {
            int mid = (st + dr) >> 1;
            if(sol[mid] <= cadran[index][i].y) {
                poz = mid;
                dr = mid - 1;
            }
            else
                st = mid + 1;
        }
        if(poz)
            sol[poz] = cadran[index][i].y;
        else
            sol.emplace_back(cadran[index][i].y);
    }
    return sol.size() - 1;
}

int32_t main() {
    fin >> N >> p.x >> p.y;
    for(int i = 0; i < N; ++i) {
        int x, y;
        fin >> x >> y;
        x -= p.x, y -= p.y;
        if(x >= 0 && y >= 0)
            cadran[0].emplace_back(x, y);
        else
            if(x < 0 && y >= 0)
                cadran[1].emplace_back(-x, y);
        else
            if(x >= 0 && y < 0)
                cadran[2].emplace_back(x, -y);
        else
            cadran[3].emplace_back(-x, -y);
    }
    for(int i = 0; i < 4; ++i)
        ans += solve(i);
    fout << ans << '\n';
}