Cod sursa(job #3345894)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 11 martie 2026 18:33:22
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
// #include <bits/std++.h>
#define in  fin
#define out fout
#define int long long

using namespace std;

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

struct punct{
    int x, y;
};

bool cmp_universal(punct &a, punct &b){
    if(a.x != b.x) return a.x < b.x;
    else return a.y < b.y;
}

int nr_de_subsecvente(vector<int> &v){
    if(v.empty()) return 0;
    vector<int> capete;
    for(int i = 0; i < v.size(); i++){

        int l = 0, r = capete.size() - 1, sol = 0;
        while(l <= r){
            int m = (l + r) / 2;
            if(capete[m] > v[i]){
                l = m + 1;
                sol = l + 1;
            }else{
                r = m - 1;
            }
        }

        if(sol == capete.size()) capete.push_back(v[i]);
        else capete[sol] = v[i];
    }
    return capete.size(); // nu e tocmai optim dar sa zicem
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    // de ce is totimpul asa tractor astea

    int n; in >> n;
    int xs, ys; in >> xs >> ys;
    vector<punct> cdr[4];
    for(int i = 0; i < n; i++){
        int x, y; in >> x >> y;
        x -= xs;
        x -= ys; // translating

        if(x < 0 && y > 0) cdr[0].push_back({-x, y});
        if(x > 0 && y > 0) cdr[1].push_back({x, y});
        if(x < 0 && y < 0) cdr[2].push_back({-x, -y});
        if(x > 0 && y < 0) cdr[3].push_back({x, -y});
    }

    // sort dupa x bine si trb sa vad cate pot face cresc cu y

    vector<int> minimude[4];
    for(int i = 0; i < 4; i++){
        sort(cdr[i].begin(), cdr[i].end(), cmp_universal);
        for(int j = 0; j < cdr[i].size(); j++){
            minimude[i].push_back(cdr[i][j].y);
        }
    }

    int total = 0;
    for(int i = 0; i < 4; i++){
        total += nr_de_subsecvente(minimude[i]);
        // cout << "i = " << i << " nr = " << nr_de_subsecvente(minimude[i]) << '\n';
        // cout << "i = " << i << " v = ";
        // for(const punct &x : cdr[i]) cout << "( " << x.x << " " << x.y << " ) ";
        // cout << '\n';
    }

    out << total << '\n';

    return 0;
}