Cod sursa(job #3335635)

Utilizator GliggyGligor Andrei Gliggy Data 23 ianuarie 2026 09:15:17
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <bits/stdc++.h>
using namespace std;

struct Point {
    long long x, y;
};

int solve_quadrant(vector<Point>& v, int q) {
    // sort by y: descending for quadrants 1 & 2, ascending for 3 & 4
    if (q == 1 || q == 2) {
        sort(v.begin(), v.end(), [](const Point& a, const Point& b) {
            return a.y > b.y; // descending
        });
    } else {
        sort(v.begin(), v.end(), [](const Point& a, const Point& b) {
            return a.y < b.y; // ascending
        });
    }

    vector<long long> best;

    for (auto& p : v) {
        long long x = p.x;
        int pos = -1;

        int l = 0, r = (int)best.size() - 1;
        while (l <= r) {
            int m = (l + r) / 2;

            bool ok;
            if (q == 1) ok = best[m] <= x;
            else if (q == 2) ok = best[m] >= x;
            else if (q == 3) ok = best[m] >= x;
            else ok = best[m] <= x;

            if (ok) {
                pos = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        if (pos == -1) {
            best.push_back(x);
        } else {
            best[pos] = x;
        }
    }

    return (int)best.size();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    int N;
    fin >> N;

    long long Ox, Oy;
    fin >> Ox >> Oy;

    vector<Point> quad[5];

    for (int i = 0; i < N; i++) {
        long long x, y;
        fin >> x >> y;

        x -= Ox;
        y -= Oy;

        if (x >= 0 && y >= 0) quad[1].push_back({x, y});
        else if (x < 0 && y >= 0) quad[2].push_back({x, y});
        else if (x < 0 && y < 0) quad[3].push_back({x, y});
        else quad[4].push_back({x, y});
    }

    int answer = 0;
    for (int q = 1; q <= 4; q++) {
        answer += solve_quadrant(quad[q], q);
    }

    fout << answer;
    return 0;
}