Cod sursa(job #3148323)

Utilizator Dragos__1_1Dragos Antohi Dragos__1_1 Data 30 august 2023 23:24:57
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.72 kb
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
#define vec vector<pair<int,int>>
using namespace std;
ifstream f("pachete.in");
ofstream g("pachete.out");
vec v[5] ;
vector<int> d;
int x , y , a , b , i , j , n , rez;
bool mycmp (pair <int,int>a,pair<int,int>b)
{   return a.first<b.first||(a.first==b.first&&a.second<b.second);
}

int calc (int l)
{   int x=v[l].size()-1,marime=0; bool ok=0;if (x<=0)return 0;
    d.push_back(v[l][0].second);
    for (int i=1;i<=x;i++)
    {   int st=0,dr=marime,poz=0,mid;
        while (st<=dr)
        {   int mid=(st+dr)/2;
            if (v[l][i].second>=d[mid])
               {dr=mid-1;            poz=mid;
                ok=1;}

            else {st=mid+1;

            }
        }
        if (ok) d[poz]=v[l][i].second;
        else d.push_back(v[l][i].second),marime++;;
        //cout<<poz<<' '<<ok<<' '<<marime<<endl;
        ok=0;

        //for (int j=0;j<=marime;j++)
        //cout<<d[i]<<' ';cout<<endl;
    }
    return marime+1;
}
int main()
{
    f>>n;
    f>>x>>y;
    for (i=1;i<=n;i++)
    {   f>>a>>b;
        a-=x;
        b-=y;
        if (a>=0)
            {   if (b>=0)
                {   v[1].push_back({a,b});//cout<<a<<' '<<b<<'!'<<endl;
                }
                else {
                    v[2].push_back({a,-b});//cout<<a<<' '<<-b<<'@'<<endl;
                }
            }
        else{
            if (b>=0)
            {   v[4].push_back({-a,b});//cout<<-a<<' '<<b<<'#'<<endl;
            }
            else {
                v[3].push_back({-a,-b});//cout<<-a<<' '<<-b<<'$'<<endl;
            }
        }
    }
    //cout<<endl;
    sort (v[1].begin(),v[1].end(),mycmp);//for(i=0;i<=int(v[1].size())-1;i++)cout<<v[1][i].first<<' '<<v[1][i].second<<endl;
    //cout<<endl;
    sort (v[2].begin(),v[2].end(),mycmp);//for(i=0;i<=int(v[2].size())-1;i++)cout<<v[2][i].first<<' '<<v[2][i].second<<endl;
    //cout<<endl;
    sort (v[3].begin(),v[3].end(),mycmp);//for(i=0;i<=int(v[3].size())-1;i++)cout<<v[3][i].first<<' '<<v[3][i].second<<endl;
    //cout<<endl;
    sort (v[4].begin(),v[4].end(),mycmp);//for(i=0;i<=int(v[4].size())-1;i++)cout<<v[4][i].first<<' '<<v[4][i].second<<endl;
    //cout<<endl;
    //cout<<calc(1)<<' '<<calc(2)<<' '<<calc(3)<<' '<<calc(4)<<' '<<calc(1)+calc(2)+calc(3)+calc(4);
    rez=calc(1)+calc(2)+calc(3)+calc(4);
    g<<rez<<'\n';
    return 0;
}