Cod sursa(job #2716765)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 5 martie 2021 17:17:16
Problema Pachete Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <bits/stdc++.h>
#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;
    for(int i = 0; i < N; ++i) {
        int st = 0, dr = sol.size() - 1, poz = -1;
        while(st <= dr) {
            int mid = (st + dr) >> 1;
            if(sol[mid] < cadran[index][i].y) {
                poz = mid;
                st = mid + 1;
            }
            else
                dr = mid - 1;
        }
        if(poz == -1)
            sol.emplace_back(cadran[index][i].y);
        else
            sol[poz] = cadran[index][i].y;
    }
    return sol.size();
}

int 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';
}