Cod sursa(job #3222813)

Utilizator unomMirel Costel unom Data 11 aprilie 2024 18:22:15
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.65 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

#define int long long

ifstream in("pachete.in");
ofstream out("pachete.out");
int n, ans, cnt;
int ox, oy;
vector<pair<int, int>> v1;
vector<pair<int, int>> v2;
vector<pair<int, int>> v3;
vector<pair<int, int>> v4;
vector<int> vec[50005];

int cauta(int x)
{
    int st = 1;
    int dr = cnt;
    int ans = -1;
    int mij;

    while(st <= dr)
    {
        mij = (st + dr) / 2;

        if(vec[mij][vec[mij].size() - 1] <= x)
        {
            ans = mij;
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }

    return ans;
}

signed main()
{
    in>>n;
    in>>ox>>oy;

    int x, y;
    for(int i = 1; i<=n; i++)
    {
        in>>x>>y;

        if(x >= ox && y >= oy)
        {
            v1.push_back({x, y});
        }
        else if(x < ox && y >= oy)
        {
            v2.push_back({x * (-1), y});
        }
        else if(x <= ox && y < oy)
        {
            v3.push_back({x * (-1), y * (-1)});
        }
        else
        {
            v4.push_back({x, y * (-1)});
        }
    }

    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    sort(v3.begin(), v3.end());
    sort(v4.begin(), v4.end());


    for(int i = 0; i<v1.size(); i++)
    {
        if(i == 0)
        {
            cnt++;
            vec[cnt].push_back(v1[i].second);
        }
        else
        {
            int poz = cauta(v1[i].second);

            if(poz == -1)
            {
                cnt++;
                vec[cnt].push_back(v1[i].second);
            }
            else
            {
                vec[poz].push_back(v1[i].second);
            }
        }
    }
    ans += cnt;

    //out<<cnt<<'\n';

    for(int i = 1; i<=cnt; i++)
    {
        vec[i].clear();
    }

    cnt = 0;
    for(int i = 0; i<v2.size(); i++)
    {
        if(i == 0)
        {
            cnt++;
            vec[cnt].push_back(v2[i].second);
        }
        else
        {
            int poz = cauta(v2[i].second);

            if(poz == -1)
            {
                cnt++;
                vec[cnt].push_back(v2[i].second);
            }
            else
            {
                vec[poz].push_back(v2[i].second);
            }
        }
    }
    ans += cnt;

    //out<<cnt<<'\n';

    for(int i = 1; i<=cnt; i++)
    {
        vec[i].clear();
    }

    cnt = 0;
    for(int i = 0; i<v3.size(); i++)
    {
        if(i == 0)
        {
            cnt++;
            vec[cnt].push_back(v3[i].second);
        }
        else
        {
            int poz = cauta(v3[i].second);

            if(poz == -1)
            {
                cnt++;
                vec[cnt].push_back(v3[i].second);
            }
            else
            {
                vec[poz].push_back(v3[i].second);
            }
        }
    }
    ans += cnt;

    //out<<cnt<<'\n';

    for(int i = 1; i<=cnt; i++)
    {
        vec[i].clear();
    }

    cnt = 0;
    for(int i = 0; i<v4.size(); i++)
    {
        if(i == 0)
        {
            cnt++;
            vec[cnt].push_back(v4[i].second);
        }
        else
        {
            int poz = cauta(v4[i].second);

            if(poz == -1)
            {
                cnt++;
                vec[cnt].push_back(v4[i].second);
            }
            else
            {
                vec[poz].push_back(v4[i].second);
            }
        }
    }
    ans += cnt;

    //out<<cnt<<'\n';

    out<<ans;

    return 0;
}