Cod sursa(job #3345875)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 11 martie 2026 17:31:24
Problema Pachete Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 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

using namespace std;

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

struct punct{
    int x, y;
};

int cadran(int x, int y){
    // 0 1
    // 2 3

    if(x < 0 && y > 0) return 0;
    if(x > 0 && y > 0) return 1;
    if(x < 0 && y < 0) return 2;
    return 3;
}

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

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

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

bool cmp_cadran_3(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;
    capete.push_back(v[0]);
    for(int i = 1; i < v.size(); i++){
        if(v[i] < capete[0]){
            capete.insert(capete.begin(), v[i]);
        }else{
            int it = upper_bound(capete.begin(), capete.end(), v[i]) - capete.begin() - 1;
            capete[it] = 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++){
        punct x; in >> x.x >> x.y;
        x.x -= xs;
        x.y -= ys;
        // cout << "( " << x.x << " , " << x.y << " ) --- cadran --- > " << cadran(x.x, x.y) << '\n';
        cdr[ cadran(x.x, x.y) ].push_back(x);
    }

    sort(cdr[0].begin(), cdr[0].end(), cmp_cadran_0);
    sort(cdr[1].begin(), cdr[1].end(), cmp_cadran_1);
    sort(cdr[2].begin(), cdr[2].end(), cmp_cadran_2);
    sort(cdr[3].begin(), cdr[3].end(), cmp_cadran_3);

    vector<int> minimude[4];
    for(int i = 0; i < 4; i++){
        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 << " mini = ";
        // for(const int &x : minimude[i]) cout << x << " ";
        // cout << '\n';
    }

    out << total << '\n';

    return 0;
}