Cod sursa(job #3286823)

Utilizator maxtraAlex Deonise maxtra Data 14 martie 2025 18:31:25
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50005;

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


int n, m, Ox, Oy;
vector<pair<int, int>> cadran[4]; // vectori pentru fiecare cadran
int k[4]; // numarul de drumuri pentru fiecare cadran
vector<int> d[4]; // retin cel mai mare Y pentru fiecare drum

// cauta binar in pozitia unde poate fi adaugat un punct intr-un drum extins
int binary_search(vector<int> &d, int y) {
    int left = 0, right = d.size() - 1, mid;
    
    while (left <= right) {
        mid = (left + right) / 2;
        
        if (d[mid] > y) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
}
    

void adauga(vector<int> &d, int y) {
    int pos = binary_search(d, y);
    
    if (pos < d.size()) {
        d[pos] = y;
    } else d.push_back(y);
    
    return;
}

int main()
{
    fin >> n >> Ox >> Oy;
    
    for (int i = 0; i < n; i++) {
        int x, y;
        fin >> x >> y;
        
        x -= Ox, y -= Oy; // translatez fata de origine
        
        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);
    }
    
    // procesare pentru fiecare cadran
    for (int i = 0; i < 4; i++) {
        sort(cadran[i].begin(), cadran[i].end()); // sortare crescator dupa x apoi dupa y
        
        for (auto &[x, y] : cadran[i]) {
            adauga(d[i], y);
        }
        
        k[i] = d[i].size(); // numarul de drumuri pentru acest cadran
    }
    
    fout << k[0] + k[1] + k[2] + k[3];

    return 0;
}