Cod sursa(job #89079)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 5 octombrie 2007 20:34:58
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.15 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 50500
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define INF 50000

vector<pair<int,int> > V;
int X[NMAX], Y[NMAX], Px, Py, N, T[2*NMAX], NrSub, P, Q;

void read()
{
        int i;
        
        freopen("pachete.in", "r", stdin);
        scanf("%d", &N);
        scanf("%d%d", &Px, &Py);
        for (i = 1; i <= N; i++)
        {
                scanf("%d%d", X+i, Y+i);
                X[i] -= Px; Y[i] -= Py;
        }
}

void number(int n)
{
        int i, x, p, q, lo, hi, md;
        
        memset(T,0,sizeof(T));
        if (n>0) NrSub++, T[p = q = INF] = V[1].s;
        for (i = 2; i <= n; i++)
        {
                if (V[i].s<T[p]) T[--p] = V[i].s, NrSub++;
                else
                {
                        md = (p+q)>>1; x = V[i].s;
                        for (lo = p, hi = q; lo <= hi; md = (lo+hi)>>1)
                        {
                                if (T[md]>x) hi = md-1;
                                else lo = md+1;
                        }
                        if (hi <= q) T[hi] = x;
                        else NrSub++;
                }
        }
}

void solve()
{
        int i, n;

        //c1
        for (i = 1; i <= N; i++)
            if (X[i]>=0&&Y[i]>=0) V.pb(mp(Y[i],i));
        sort(V.begin(), V.end());
        n = V.size();
        for (i = 0; i < n; i++) Y[ V[i].s ] = i+1;
        V.clear();
        V.pb(mp(-NMAX,-NMAX));
        for (i = 1; i <= N; i++)
            if (X[i]>=0&&Y[i]>=0) V.pb(mp(X[i],Y[i]));
        sort(V.begin(), V.end());
        number(n);

        //c2
        V.clear();
        for (i = 1; i <= N; i++)
            if (X[i]>=0&&Y[i]<0) V.pb(mp(Y[i],i));
        sort(V.begin(), V.end());
        n = V.size();
        for (i = 0; i < n; i++) Y[ V[i].s ] = -(i+1);
        V.clear();
        V.pb(mp(-NMAX,-NMAX));
        for (i = 1; i <= N; i++)
            if (X[i]>=0&&Y[i]<0) V.pb(mp(X[i],-Y[i]));
        sort(V.begin(), V.end());
        number(n);

        //c3
        V.clear();
        for (i = 1; i <= N; i++)
            if (X[i]<0&&Y[i]<0) V.pb(mp(Y[i],i));
        sort(V.begin(), V.end());
        n = V.size();
        for (i = 0; i < n; i++) Y[ V[i].s ] = -(i+1);
        V.clear();
        V.pb(mp(-NMAX,-NMAX));
        for (i = 1; i <= N; i++)
            if (X[i]<0&&Y[i]<0) V.pb(mp(X[i],-Y[i]));
        sort(V.begin(), V.end());
        number(n);

        //c4
        V.clear();
        for (i = 1; i <= N; i++)
            if (X[i]<0&&Y[i]<0) V.pb(mp(Y[i],i));
        sort(V.begin(), V.end());
        n = V.size();
        for (i = 0; i < n; i++) Y[ V[i].s ] = -(i+1);
        V.clear();
        V.pb(mp(-NMAX,-NMAX));
        for (i = 1; i <= N; i++)
            if (X[i]<0&&Y[i]<0) V.pb(mp(X[i],-Y[i]));
        sort(V.begin(), V.end());
        number(n);
}

void write()
{
        freopen("pachete.out", "w", stdout);
        printf("%d\n", NrSub);
}

int main()
{
        read();
        solve();
        write();
        return 0;
}