Cod sursa(job #475590)

Utilizator freak93Adrian Budau freak93 Data 7 august 2010 16:31:38
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<fstream>
#include<algorithm>
#define x first
#define y second
using namespace std;

const char iname[]="pachete.in";
const char oname[]="pachete.out";
const int maxn=52000;

ifstream f(iname);
ofstream g(oname);

int i,n,deque[maxn],k,j,step,s[2],rez;
pair<int,int> a[maxn];

void rot(pair<int,int> &a)
{
    int aux;
    aux=a.x;a.x=a.y;a.y=-aux;
}

int main()
{
    f>>n;
    f>>s[0]>>s[1];
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y,a[i].x-=s[0],a[i].y-=s[1];
    k=0;
    sort(a+1,a+n+1);
    for(i=1;i<=n;++i)
        if(a[i].x>0&&a[i].y>0)
        {
            for(step=1;step<k;step<<=1);
            for(j=0;step;step>>=1)
                if(j+step<=k&&a[deque[j+step]].y>a[i].y)
                    j+=step;
            if(j==k)
                ++k;
            deque[j+1]=i;
        }
    rez+=k;

    for(i=1;i<=n;++i)
        rot(a[i]);
    k=0;
    sort(a+1,a+n+1);
    for(i=1;i<=n;++i)
        if(a[i].x>0&&a[i].y>0)
        {
            for(step=1;step<k;step<<=1);
            for(j=0;step;step>>=1)
                if(j+step<=k&&a[deque[j+step]].y>a[i].y)
                    j+=step;
            if(j==k)
                ++k;
            deque[j+1]=i;
        }
    rez+=k;

    for(i=1;i<=n;++i)
        rot(a[i]);
    k=0;
    sort(a+1,a+n+1);
    for(i=1;i<=n;++i)
        if(a[i].x>0&&a[i].y>0)
        {
            for(step=1;step<k;step<<=1);
            for(j=0;step;step>>=1)
                if(j+step<=k&&a[deque[j+step]].y>a[i].y)
                    j+=step;
            if(j==k)
                ++k;
            deque[j+1]=i;
        }
    rez+=k;

    for(i=1;i<=n;++i)
        rot(a[i]);
    k=0;
    sort(a+1,a+n+1);
    for(i=1;i<=n;++i)
        if(a[i].x>0&&a[i].y>0)
        {
            for(step=1;step<k;step<<=1);
            for(j=0;step;step>>=1)
                if(j+step<=k&&a[deque[j+step]].y>a[i].y)
                    j+=step;
            if(j==k)
                ++k;
            deque[j+1]=i;
        }
    rez+=k;

    g<<rez<<"\n";
}