Cod sursa(job #3167660)

Utilizator barbuionBarbu Ion barbuion Data 10 noiembrie 2023 22:59:43
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <algorithm>
///cate componente cu nr max de elem si care sunt
using namespace std;
ifstream in("pachete.in");
ofstream out("pachete.out");
int n,x,y,k1,k2,k3,k4;
struct punct{
  int x,y;
}v[50001],a[50001],b[50001],c[50001],d[50001];
int A[50001];
int cmp(punct a, punct b){
   if(a.x==b.x)
       return a.y<b.y;
   return a.x<b.x;
}
int cautbin(punct a[], int n){
   sort(a+1,a+n+1,cmp);
   int k=1;
   A[k]=a[1].y;
int   st=1,dr=n;

   for(int i=2;i<=n;i++)
      if(a[i].y<A[k]){
        A[++k]=a[i].y;
      }
      else
      {
         int st=1,dr=k;
         while(st<=dr){
            int mid=(st+dr)/2;
            if(a[i].y>=A[mid])
                 dr=mid-1;
            else
                st=mid+1;
         }
         A[st]=a[i].y;
      }
      return k;
}
int main()
{
    in>>n;
    in>>x>>y;
    for(int i=1;i<=n;i++){
        in>>v[i].x>>v[i].y;
        v[i].x-=x;
        v[i].y-=y;
        if(v[i].x>=0&&v[i].y>=0){
            a[++k1]={v[i].x,v[i].y};
        }
        else
        if(v[i].x>=0&&v[i].y<0){
            b[++k2]={v[i].x,-v[i].y};
        }
        else
        if(v[i].x<0&& v[i].y>0){
            c[++k3]={-v[i].x,v[i].y};
        }
        else{
            d[++k4]={-v[i].x,-v[i].y};
        }
    }
int    sol=0;
if(k1>0)
sol=cautbin(a,k1);
if(k2>0)
    sol+=cautbin(b,k2);
    if(k3>0)
    sol+=cautbin(c,k3);
    if(k4>0)
    sol+=cautbin(d,k4);
    out<<sol;
    return 0;
}