Cod sursa(job #3168152)

Utilizator dorupopDoru Pop dorupop Data 11 noiembrie 2023 17:07:03
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<algorithm>
#include<fstream>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
struct punct{
   int x,y;
}v[50001],c1[50001],c2[50001],c3[50001],c4[50001];
int n,xf,yf,k1,k2,k3,k4;

int cmp(punct a, punct b){
  if(a.x==b.x)
      return a.y<b.y;
  return a.x<b.x;
}
int a[50001];

int solve(punct v[], int n){

   sort(v+1,v+n+1,cmp);
   int k=1;
   a[1]=v[1].y;
   for(int i=2;i<=n;i++){
      /// caut binar in vectorul a (ordonat descrescator) cea mai mare valoare <v[i].y
      int st=1, dr=k, poz=0;
      while(st<=dr)
      {
          int mid=(st+dr)/2;
          if(a[mid]<=v[i].y)
          {
              poz=mid;
              dr=mid-1;
          }
          else
              st=mid+1;
      }
      if(poz!=0)
          a[poz]=v[i].y;
      else
         a[++k]=v[i].y;
   }
  return k;
}

int main(){
    fin>>n>>xf>>yf;
    for(int i=1;i<=n;i++){
        fin>>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 nrdrum=0;
    if(k1!=0)
         nrdrum=solve(c1,k1);
    if(k2!=0)
         nrdrum+=solve(c2,k2);
    if(k3!=0)
         nrdrum+=solve(c3,k3);
   if(k4!=0)
         nrdrum+=solve(c4,k4);
fout<<nrdrum;
return 0;
}