Cod sursa(job #3168234)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 11 noiembrie 2023 19:54:26
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("pachete.in");
ofstream cout("pachete.out");
int n,i,j,st,dr,mid,xf,yf,k1,k2,k3,k4,a[50001];
struct pct{
int x,y;
}v[50001],c1[50001],c2[50001],c3[50001],c4[50001];
bool cmp(pct a,pct b){
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
int solve(pct v[],int n){
    sort(v+1,v+n+1,cmp);
    int k=1;
    a[1]=v[1].y;
    for(i=2;i<=n;i++)
    {
        int st=1,dr=k,p=0;
        while(st<=dr){
            int mid=(st+dr)/2;
            if(a[mid]<=v[i].y)
            {
                p=mid;
                dr=mid-1;
            }
            else
                st=mid+1;
        }
        if(p!=0)
            a[p]=v[i].y;
        else
            a[++k]=v[i].y;
    }
    return k;
}
int main()
{
    cin>>n>>xf>>yf;
    for(i=1;i<=n;i++){
        cin>>v[i].x>>v[i].y;
        v[i].x-=xf;
        v[i].y-=yf;
        if(v[i].x>=0&&v[i].y>=0)
            c1[++k1]={v[i].x,v[i].y};
        else if(v[i].x>=0&&v[i].y<0)
            c2[++k2]={v[i].x,-v[i].y};
        else if(v[i].x<0&&v[i].y<0)
            c3[++k3]={-v[i].x,-v[i].y};
        else
            c4[++k4]={-v[i].x,v[i].y};
    }
    int sol=0;
    if(k1!=0)
        sol=solve(c1,k1);
    if(k2!=0)
        sol+=solve(c2,k2);
    if(k3!=0)
        sol+=solve(c3,k3);
    if(k4!=0)
        sol+=solve(c4,k4);
    cout<<sol;
    return 0;
}