Cod sursa(job #3360819)

Utilizator IzabelaJePloscaru Maria Izabela IzabelaJe Data 16 iulie 2026 20:49:56
Problema Pachete Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
int n,sol;
struct coord{
    int x,y;
};
coord start;
coord v[50001];
int cadr1[50001],cadr2[50001],cadr3[50001],cadr4[50001];
int c1,c2,c3,c4;
int d1[50001],d2[50001],d3[50001],d4[50001];
int sortarex(const coord &a,const coord &b){
    if(a.x==b.x)
        return a.y<b.y;
    else
        return a.x<b.x;
}
int parcurgere1(int cadr1[],int c1,int d1[]){
    int st,dr,mid;
    int k1=0;
    for(int i=1;i<=c1;i++){
        int x=cadr1[i];
        st=1; dr=k1;
        while(st<=dr){
            mid=(st+dr)/2;
            if(x<=d1[mid])
                st=mid+1;
            else
                dr=mid-1;
            }
        if(st==k1+1)
            d1[++k1]=x;
        else
            d1[st]=x;
    }
    return k1;
}

int main()
{
    fin>>n;
    fin>>start.x>>start.y;
    for(int i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
        v[i].x-=start.x;
        v[i].y-=start.y;
    }
    sort(v+1,v+n+1,sortarex);
    for(int i=1;i<=n;i++){
        if(v[i].x>0){
            if(v[i].y>0)
                cadr1[++c1]=v[i].y;
            else
                cadr4[++c4]=v[i].y;
        }
        else{
            if(v[i].y>0)
                cadr2[++c2]=v[i].y;
            else
                cadr3[++c3]=v[i].y;
        }
    }
    reverse(cadr2+1,cadr2+c2+1);
    reverse(cadr3+1,cadr3+c3+1);
    sol+=parcurgere1(cadr1,c1,d1);
    sol+=parcurgere1(cadr2,c2,d2);
    sol+=parcurgere1(cadr3,c3,d3);
    sol+=parcurgere1(cadr4,c4,d4);
    fout<<sol;
    return 0;
}