Cod sursa(job #3222768)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 11 aprilie 2024 16:44:35
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <set>
#include <cmath>
#include <stack>
#include <vector>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <unordered_map>
#include <map>
#define ll long long

using namespace std;

ifstream cin("pachete.in");
ofstream cout("pachete.out");

const int NMAX = 5e4;

struct Point
{
    int x, y;
    void Read()
    {
        cin >> x >> y;
    }
    void Translate(Point to_whom)
    {
        x -= to_whom.x;
        y -= to_whom.y;
    }
};

int n, answer;
Point origin, points[NMAX + 1];
vector<Point> points_cadran[5];

bool cmpP(const Point& a, const Point& b)
{
    if (a.x < b.x)
        return true;
    if (a.x == b.x && a.y < b.y)
        return true;
    return false;
}

int BS(vector<int>& a, int value)
{
    int left = 0, right = a.size() - 1, pos = -1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (a[mid] <= value)
            pos = mid, right = mid - 1;
        else
            left = mid + 1;
    }
    return pos;
}

int Solve(vector<Point>& points)
{
    if (points.size() == 0)
        return 0;

    int n = points.size();
    sort(points.begin(), points.end(), cmpP);
    
    vector<int> subsq;
    subsq.push_back(points[0].y);
    for (int i = 1; i < n; i++)
    {
        if (points[i].y < subsq.back())
            subsq.push_back(points[i].y);
        else
        {
            int pos = BS(subsq, points[i].y);
            assert(pos != -1);
            subsq[pos] = points[i].y;
        }
    }

    return subsq.size();
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    origin.Read();
    for (int i = 1; i <= n; i++)
        points[i].Read();

    for (int i = 1; i <= n; i++)
        points[i].Translate(origin);

    for (int i = 1; i <= n; i++)
    {
        bool sign_x = (points[i].x >= 0);
        bool sign_y = (points[i].y >= 0);
        if (sign_x && sign_y)
            points_cadran[1].push_back(points[i]);
        else if (!sign_x && sign_y)
            points_cadran[2].push_back({ -points[i].x, points[i].y });
        else if (!sign_x && !sign_y)
            points_cadran[3].push_back({ -points[i].x, -points[i].y });
        else
            points_cadran[4].push_back({ points[i].x, -points[i].y });
    }

    for (int i = 1; i <= 4; i++)
        answer += Solve(points_cadran[i]);
    cout << answer;

    return 0;
}