Cod sursa(job #8508)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 24 ianuarie 2007 21:37:57
Problema Pachete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 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], D[NMAX], F[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 = 0; j < NMAX; j++) H[j] = INF, D[i] = F[i] = Pred[i] = 0;
                H[0] = 0;
                H[1] = 0; N = Cadran[i].size();
                D[0] = 1;
                L = 1;
                for (j = 1; j < N; j++)
                {
                    p = search(i, Cadran[i][j].second);
                    Pred[j] = H[p];
                    D[j] = p+1;
                    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;
                }
                if (N > 0)
                {
                        for (j = N-1; j >= 0; j--)
                            if (F[j]==0)
                            {
                                p = j;
                                while (Pred[p] != p) F[p] = 1, p = Pred[p];
                                F[p] = 1;
                                Num++;
                            }
                }
        }

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

        return 0;
        
}