Cod sursa(job #3168221)

Utilizator nicushor21Pirlog Marian Nicolae nicushor21 Data 11 noiembrie 2023 19:35:34
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct punct{
    int x,y;
};
int cmp(punct a,punct b){
    if(a.x==b.x){
        return a.y<b.y;
    }else{
        return a.x<b.x;
    }
}
int s[50001];
int solve(punct v[],int l){
    int st,dr,k=0,mid,poz,i;
    sort(v,v+l,cmp);
    for(i=1;i<l;i++){
        st=1;dr=k;poz=k+1;
        while(st<=dr){
            mid=(st+dr)/2;
            if(s[mid]<=v[i].y){
                dr=mid-1;
                poz=mid;
            }else{
                st=mid+1;
            }
        }
        if(poz!=k+1){
            s[poz]=v[i].y;
        }else{
            s[poz]=v[i].y;
            k++;
        }
    }
    return k;
}
punct c1[50001],c2[50001],c3[50001],c4[50001];
int n,x,y,Sx,Sy,cnt1=1,cnt2=1,cnt3=1,cnt4=1,i,nrdr;
int main()
{
    ifstream fin("pachete.in");
    ofstream fout("pachete.out");
    fin>>n;
    fin>>Sx>>Sy;
    for(i=0;i<n;i++){
        fin>>x>>y;
        if(x>=Sx&&y>=Sy){
            c1[cnt1]={x-Sx,y-Sy};
            cnt1++;
        }else if(x>=Sx&&y<Sy){
            c2[cnt2]={x-Sx,-(y-Sy)};
            cnt2++;
        }else if(x<Sx&&y<Sy){
            c3[cnt3]={-(x-Sx),-(y-Sy)};
            cnt3++;
        }else{
            c4[cnt4]={-(x-Sx),y-Sy};
            cnt4++;
        }
    }
    if(cnt1!=0){
        nrdr=solve(c1,cnt1);
    }
    if(cnt2!=0){
        nrdr+=solve(c2,cnt2);
    }
    if(cnt3!=0){
        nrdr+=solve(c3,cnt3);
    }
    if(cnt4!=0){
        nrdr+=solve(c4,cnt4);
    }
    fout<<nrdr;
    fin.close();
    fout.close();
    return 0;
}