Cod sursa(job #1936840)

Utilizator tgm000Tudor Mocioi tgm000 Data 23 martie 2017 14:59:06
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct punct{int x,y;};
punct a1[50001];
punct a2[50001];
punct a3[50001];
punct a4[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 cauta(punct a[],int k){
  if(k==0)
    return 0;
  int t,i,st,dr,m,poz;
  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;
    }
  }
  return t;
}
int main(){
  int n,xp,yp,k1,k2,k3,k4,i,x,y;
  freopen("pachete.in","r",stdin);
  freopen("pachete.out","w",stdout);
  scanf("%d%d%d",&n,&xp,&yp);
  k1=k2=k3=k4=0;
  for(i=1;i<=n;i++){
    scanf("%d%d",&x,&y);
    x-=xp;
    y-=yp;
    if(x>0&&y>=0){
      k1++;
      a1[k1].x=x;
      a1[k1].y=y;
    }else if(x<=0&&y>=0){
      k2++;
      a2[k2].x=-x;
      a2[k2].y=y;
    }else if(x<=0&&y<0){
      k3++;
      a3[k3].x=-x;
      a3[k3].y=-y;
    }else if(x>0&&y<0){
      k4++;
      a4[k4].x=x;
      a4[k4].y=-y;
    }
  }
  printf("%d",cauta(a1,k1)+cauta(a2,k2)+cauta(a3,k3)+cauta(a4,k4));
  return 0;
}