Cod sursa(job #473785)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 31 iulie 2010 22:05:20
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define maxim(a,b) (a>b ? a : b)

int n,sol,poz,el[4];
int vec[50006],nr;

struct point
{
    int x,y;
};
point cad[4][50006],p;

int cmp(const point& a,const point& b)
{
    return (a.x<b.x);
}

int cmp2(const point& a,const point& b)
{
    return (a.x>b.x);
}

int main ()
{
    int i,t,st,dr,m;
    point a;
    freopen("pachete.in","r",stdin);
    freopen("pachete.out","w",stdout);
    scanf("%d",&n);
    scanf("%d%d",&p.x,&p.y);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&a.x,&a.y);
        if(a.x>p.x && a.y>p.y)
            cad[0][++el[0]]=a;
        if(a.x>p.x && a.y<p.y)
            cad[1][++el[1]]=a;
        if(a.x<p.x && a.y<p.y)
            cad[2][++el[2]]=a;
        if(a.x<p.x && a.y>p.y)
            cad[3][++el[3]]=a;
    }

    for(i=1;i<=el[1];i++)
        cad[1][i].y*=-1;
    for(i=1;i<=el[2];i++)
    {
        cad[2][i].x*=-1;
        cad[2][i].y*=-1;
    }
    for(i=1;i<=el[3];i++)
        cad[3][i].x*=-1;
    
    for(t=0;t<4;t++)
    {
        if(!el[t])
            continue;
        sort(cad[t]+1,cad[t]+el[t]+1,cmp);
        vec[nr=1]=cad[t][1].y;
        for(i=2;i<=el[t];i++)
        {
            st=1;dr=nr;poz=nr+1;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(vec[m]<cad[t][i].y)
                {
                    poz=m;
                    dr=m-1;
                }
                else
                    st=m+1;
            }
            vec[poz]=cad[t][i].y;
            nr=maxim(nr,poz);
        }
        sol+=nr;
    }
    printf("%d\n",sol);
    return 0;
}