Cod sursa(job #8484)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 24 ianuarie 2007 21:04:04
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 50500
#define min(a, b) ((a) < (b) ? (a):(b))
#define HMAX (1<<16)
#define INF 2000000001

using namespace std;

int N, X, Y, Num, H[NMAX], L, Pred[NMAX], T[NMAX];
vector<pair<int, int> > Cadran[4];

int search(int c, int x)
{
        int mij, p1, p2, p = 0;

        for (p1 = 0, p2 = L, mij = (p1+p2)/2; p1 <= p2; mij = (p1+p2)/2)
        {
                if (Cadran[c][ H[mij] ].second > x) p2 = mij-1;
                else p1 = mij+1, p = mij;
        }
        return p;
}

int main()
{
        int i, x, y, j, p;

        freopen("pachete.in", "r", stdin);
        scanf("%d %d %d", &N, &X, &Y);
        
        for (i = 0; i < N; i++)
        {
                scanf("%d %d", &x, &y);
                x -= X; y -= Y;
                if (x >= 0 && y >= 0) Cadran[0].push_back(make_pair(abs(x), abs(y)));
                if (x >= 0 && y < 0) Cadran[1].push_back(make_pair(abs(x), abs(y)));
                if (x < 0 && y < 0) Cadran[2].push_back(make_pair(abs(x), abs(y)));
                if (x < 0 && y >= 0) Cadran[3].push_back(make_pair(abs(x), abs(y)));
        }

        for (i = 0; i < 4; i++)
        {
                sort(Cadran[i].begin(), Cadran[i].end());
                for (j = 1; j < NMAX; j++) H[j] = INF;
                H[1] = 0; N = Cadran[i].size();
                if (N > 0) Num++;
                L = 1;
                for (j = 1; j < N; j++)
                {
                    p = search(i, Cadran[i][j].second);
                    Pred[j] = H[p];
                    if (H[p+1] < INF)
                        H[p+1] = ((Cadran[i][ H[p+1] ].second > Cadran[i][j].second) ? j:H[p+1]);
                    else L++, H[p+1] = j;
                }
                for (i = 1; i < N; i++)
                    T[ Pred[i] ]++;
                for (i = 0; i < N; i++)
                    Num += (T[i]>1);
        }

        freopen("pachete.out", "w", stdout);
        printf("%d\n", Num);

        return 0;
        
}