Cod sursa(job #3138457)

Utilizator Traian_7109Traian Mihai Danciu Traian_7109 Data 19 iunie 2023 18:02:48
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define pii pair<int, int>

using namespace std;

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

const int NMAX = 5e4;
int ox, oy;
vector<pii> zone1, zone2, zone3, zone4;
int srt[NMAX+5];

pii mp(const int &x, const int &y)
{
    pii Return;
    Return.first = x;
    Return.second = y;
    return Return;
}

pii abs_pii(const pii &value)
{
    pii Return;
    Return.first = abs(value.first);
    Return.second = abs(value.second);
    return Return;
}

class Position {
    private:
        int x, y;
        
        void read()
        {
            fin>>x>>y;
        }
        
        void solve()
        {
            x -= ox, y -= oy;
            
            if (x >= 0 && y >= 0) zone1.push_back(mp(x, y));
            if (x <  0 && y >= 0) zone2.push_back(mp(x, y));
            if (x <  0 && y <  0) zone3.push_back(mp(x, y));
            if (x >= 0 && y <  0) zone4.push_back(mp(x, y));
        }
    
    public:
        Position()
        {
            read(), solve();
        }
};

int solve(vector<pii> &v)
{
    for (auto &it : v) it = abs_pii(it);
    
    sort(v.begin(), v.end());
    int length = 0;

    for (auto it : v) {
        int position = length+1, left = 1, right = length;

        while (left <= right) {
            int middle = (left+right)/2;

            if (srt[middle] <= it.second) position = middle, right = middle-1;
            else left = middle+1;
        }

        if (position == length+1) length++;

        srt[position] = it.second;
    }

    return length;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);
    
    int n;
    fin>>n>>ox>>oy;
    
    while (n--) Position current;
    
    fout<<solve(zone1)+solve(zone2)+solve(zone3)+solve(zone4);
    return 0;
}