Cod sursa(job #1936830)

Utilizator tgm000Tudor Mocioi tgm000 Data 23 martie 2017 14:43:13
Problema Pachete Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct punct{int x,y;};
punct a[50001];
bool cmp(punct a,punct b){
  if(a.x<b.x)
    return true;
  else if(a.x>b.x)
    return false;
  else if(a.y<b.y)
    return true;
  else
    return false;
}
int v[50001];
int main(){
  int n,xp,yp,nr,k,i,x,y,t,st,dr,m,poz;
  freopen("pachete.out","w",stdout);
  nr=0;

  //cadranul 1
  freopen("pachete.in","r",stdin);
  scanf("%d%d%d",&n,&xp,&yp);
  k=0;
  for(i=1;i<=n;i++){
    scanf("%d%d",&x,&y);
    x-=xp;
    y-=yp;
    if(x>0&&y>=0){
      k++;
      a[k].x=x;
      a[k].y=y;
    }
  }
  if(k>0){
    sort(a+1,a+k+1,cmp);
    v[1]=a[1].y;
    t=1;
    for(i=2;i<=k;i++){
      if(a[i].y<v[t]){
        t++;
        v[t]=a[i].y;
      }else{
        st=1;
        dr=t;
        while(st<=dr){
          m=(st+dr)/2;
          if(a[i].y>=v[m]){
            poz=m;
            dr=m-1;
          }else
            st=m+1;
        }
        v[poz]=a[i].y;
      }
    }
    nr+=t;
  }

  //cadranul 2
  freopen("pachete.in","r",stdin);
  scanf("%d%d%d",&n,&xp,&yp);
  k=0;
  for(i=1;i<=n;i++){
    scanf("%d%d",&x,&y);
    x-=xp;
    y-=yp;
    if(x<=0&&y>=0){
      k++;
      a[k].x=-x;
      a[k].y=y;
    }
  }
  if(k>0){
    sort(a+1,a+k+1,cmp);
    v[1]=a[1].y;
    t=1;
    for(i=2;i<=k;i++){
      if(a[i].y<v[t]){
        t++;
        v[t]=a[i].y;
      }else{
        st=1;
        dr=t;
        while(st<=dr){
          m=(st+dr)/2;
          if(a[i].y>=v[m]){
            poz=m;
            dr=m-1;
          }else
            st=m+1;
        }
        v[poz]=a[i].y;
      }
    }
    nr+=t;
  }

  //cadranul 3
  freopen("pachete.in","r",stdin);
  scanf("%d%d%d",&n,&xp,&yp);
  k=0;
  for(i=1;i<=n;i++){
    scanf("%d%d",&x,&y);
    x-=xp;
    y-=yp;
    if(x<=0&&y<0){
      k++;
      a[k].x=-x;
      a[k].y=-y;
    }
  }
  if(k>0){
    sort(a+1,a+k+1,cmp);
    v[1]=a[1].y;
    t=1;
    for(i=2;i<=k;i++){
      if(a[i].y<v[t]){
        t++;
        v[t]=a[i].y;
      }else{
        st=1;
        dr=t;
        while(st<=dr){
          m=(st+dr)/2;
          if(a[i].y>=v[m]){
            poz=m;
            dr=m-1;
          }else
            st=m+1;
        }
        v[poz]=a[i].y;
      }
    }
    nr+=t;
  }

  //cadranul 4
  freopen("pachete.in","r",stdin);
  scanf("%d%d%d",&n,&xp,&yp);
  k=0;
  for(i=1;i<=n;i++){
    scanf("%d%d",&x,&y);
    x-=xp;
    y-=yp;
    if(x>0&&y<0){
      k++;
      a[k].x=x;
      a[k].y=-y;
    }
  }
  if(k>0){
    sort(a+1,a+k+1,cmp);
    v[1]=a[1].y;
    t=1;
    for(i=2;i<=k;i++){
      if(a[i].y<v[t]){
        t++;
        v[t]=a[i].y;
      }else{
        st=1;
        dr=t;
        while(st<=dr){
          m=(st+dr)/2;
          if(a[i].y>=v[m]){
            poz=m;
            dr=m-1;
          }else
            st=m+1;
        }
        v[poz]=a[i].y;
      }
    }
    nr+=t;
  }

  printf("%d",nr);
  return 0;
}