Cod sursa(job #8921)

Utilizator georgianaGane Andreea georgiana Data 25 ianuarie 2007 22:45:24
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <stdio.h>
#include <string.h>

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

void qSort(int st, int dr)
{
     int i=st, j=dr, m=x[h[(i+j)/2]];
     do
     {
         while (x[h[i]]<m) i++;
         while (x[h[j]]>m) j--;
         if (i<=j)
         {
             int aux=x[h[i]]; x[h[i]]=x[h[j]]; x[h[j]]=aux;
                 aux=y[h[i]]; y[h[i]]=y[h[j]]; y[h[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 (int i=0;i<n;i++) scanf("%d %d",&x[i],&y[i]);
    int nrtot=0;
    for (int ki=1;ki<=4;ki++)
    {
        int nr=0;
        for (int i=0;i<n;i++)
        switch (ki)
        {
            case 1: if (x[i]>xp && y[i]>yp) h[nr++]=i; break;
            case 2: if (x[i]<xp && y[i]>yp) h[nr++]=i; break;
            case 3: if (x[i]<xp && y[i]<yp) h[nr++]=i; break;
            case 4: if (x[i]>xp && y[i]<yp) h[nr++]=i; break;
        }
        qSort(0,nr-1);
        
        int cate=0;
        for (int i=0;i<nr;i++)
        {
            int st=0, dr=cate-1, k=-1, aux=y[h[i]];
            while (st<=dr)
            {
                int m=(st+dr)/2;
                if (ult[m]>aux) st=m+1;
                else k=m, dr=m-1;   
            }
            if (k<0) ult[cate++]=aux;
            else ult[k]=aux;
        }
        nrtot+=cate;
    }
    

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