Cod sursa(job #9056)

Utilizator georgianaGane Andreea georgiana Data 26 ianuarie 2007 16:11:12
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <stdio.h>
#include <string.h>

long int i,n,xp,yp,x[50000],y[50000],ult[50000];

void qSort(int st, int dr)
{
     int i=st, j=dr, m=x[(i+j)/2];
     do
     {
         while (x[i]<m) i++;
         while (x[j]>m) j--;
         if (i<=j)
         {
             int aux=x[i]; x[i]=x[j]; x[j]=aux;
                 aux=y[i]; y[i]=y[j]; y[j]=aux;
             i++; j--;         
         }
     } 
     while (i<=j);
     if (st<j) qSort(st,j);
     if (i<dr) qSort(i,dr);
}

int main()
{
    freopen("pachete.in","r",stdin);
    scanf("%d %d %d\n",&n,&xp,&yp);
    for (i=0;i<n;i++) scanf("%d %d",&x[i],&y[i]);
    qSort(0,n-1);
    long int nrtot=0;

    int cate=0;
    for (i=0;i<n;i++)
         if (x[i]>=xp && y[i]>=yp)
         {
             long int st=0,dr=cate-1,k=cate;
             while (st<=dr)
             {
                 long int m=(st+dr)/2;
                 if (ult[m]>y[i]) st=m+1;
                 else k=m, dr=m-1;
             }
             ult[k]=y[i];
             if (k==cate) cate++;
         }
    nrtot+=cate;

    cate=0;
    for (i=n-1;i>=0;i--)
         if (x[i]<=xp && y[i]>=yp)
         {
             long int st=0,dr=cate-1,k=cate;
             while (st<=dr)
             {
                 long int m=(st+dr)/2;
                 if (ult[m]>y[i]) st=m+1;
                 else k=m, dr=m-1;
             }
             ult[k]=y[i];
             if (k==cate) cate++;
         }
    nrtot+=cate;
    
    cate=0;
    for (i=n-1;i>=0;i--)
         if (x[i]<=xp && y[i]<=yp)
         {
             long int st=0,dr=cate-1,k=cate;
             while (st<=dr)
             {
                 long int m=(st+dr)/2;
                 if (ult[m]<y[i]) st=m+1;
                 else k=m, dr=m-1;
             }
             ult[k]=y[i];
             if (k==cate) cate++;
         }
    nrtot+=cate;
    
    cate=0;
    for (i=0;i<n;i++)
         if (x[i]>=xp && y[i]<=yp)
         {
             long int st=0,dr=cate-1,k=cate;
             while (st<=dr)
             {
                 long int m=(st+dr)/2;
                 if (ult[m]<y[i]) st=m+1;
                 else k=m, dr=m-1;
             }
             ult[k]=y[i];
             if (k==cate) cate++;
         }
    nrtot+=cate;

    freopen("pachete.out","w",stdout);
    printf("%d\n",nrtot);
    fclose(stdout);
    return 0;
}