Cod sursa(job #8402)

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

using namespace std;

int N, X, Y, maxX, maxY, Num, H[2*HMAX];
vector<pair<int, int> > Cadran[4];

void update(int n, int x, int v)
{
        int nod = HMAX+x;

        H[nod] = x;

        while (nod>1)
        {
                nod /= 2;
                H[nod] = ((Cadran[n][ H[2*nod] ].second < Cadran[n][ H[2*nod+1] ].second) ? H[2*nod]:H[2*nod+1]);
        }
}

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

        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());
                memset(H, 0, sizeof(H));
                update(i, 0, Cadran[i][0].second);
                if (Cadran[i].size() > 0) Num++;
                for (j = 1; j < Cadran[i].size(); j++)
                {
                        x = Cadran[i][j].first; y = Cadran[i][j].second;
                        if (Cadran[i][ H[1] ].second > y) Num++;
                        else
                        {
                                Cadran[i][ H[1] ].second = INF;
                                update(i, H[1], INF);
                        }
                        update(i, j, y);
                }
        }

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

        return 0;
        
}