Cod sursa(job #89099)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 5 octombrie 2007 21:45:26
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.11 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 compute(int d)
{
        int i, t, n = V.size();
        
        if (n>0) { t = 1;
        Y[ V[0].s ] = d*t;
        for (i = 1; i < n; i++)
        {
            if (V[i].f!=V[i-1].f) t++;
            Y[ V[i].s ] = d*t;
        }
        V.clear(); V.pb(mp(-NMAX,-NMAX)); }
}

void solve()
{
        int i, t;

        //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());
        compute(1);
        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(V.size());

        //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());
        compute(-1);
        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(V.size());

        //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());
        compute(-1);
        for (i = 1; i <= N; i++)
            if (X[i]<0&&Y[i]<0) V.pb(mp(-X[i],Y[i]));
        for (i = 0; i < V.size(); i++) V[i].s = -= V[i].s
        sort(V.begin(), V.end());
        number(V.size());

        //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());
        compute(1);
        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(V.size());
}

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

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