Cod sursa(job #8259)

Utilizator sandyxpSanduleac Dan sandyxp Data 23 ianuarie 2007 23:35:44
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

#define FIN "pachete.in"
#define FOUT "pachete.out"
#define MAXN 50001
#define ul unsigned long
#define dist(i,j) (abs(X[i] - X[j]) + abs(Y[i] - Y[j]))

typedef struct { int x, y; } coord;

int dx[]={ 1, 1,-1,-1},
    dy[]={ 1,-1,-1, 1};
int n, grad[4];
coord Dest[4][MAXN], src;
int Drum_UltY[MAXN];

bool operator<(const coord &A, const coord &B) {
    return A.x < B.x;
}

void citire()
{
    int i, c;
    coord pct;
    freopen(FIN, "r", stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d\n%d %d", &n, &src.x, &src.y);
    for (i=1; i<=n; ++i) {
        scanf("%d %d", &pct.x, &pct.y);
        pct.x -= src.x; pct.y -= src.y;
        c = (pct.x < 0) ^ (pct.y < 0);
        if (pct.x < 0) c += 2, pct.x = -pct.x;
        if (pct.y < 0) pct.y = -pct.y;
        
        Dest[c][ grad[c] ++ ] = pct;
    }
}

int bcaut_desc(int l, int r, int val) {
    int i, step, N = r-l;

    for (step=1; step < N; step <<= 1) ;
    for (i=N; step; step >>= 1)
        if (i-step >= 0 && Drum_UltY[l + (i-step)] <= val)
            i -= step;
    return l + i;
}

void rez()
{
    int i, j, poz, drumuri, dr_total = 0;

    for (i=0; i<4; ++i) { // incearca toate cadranele...
        if (!grad[i]) continue;
        std::sort(Dest[i], Dest[i] + grad[i]);
        Drum_UltY[(drumuri = 0) ++ ] = Dest[i][0].y;
        for (j=1; j < grad[i]; ++j) {
            // caut cel mai din dreapta drum in Drum_UltY cu Y<=Dest[i][j].y
            poz = bcaut_desc(0, drumuri, Dest[i][j].y);
            if (poz == drumuri) ++drumuri;
            Drum_UltY[poz] = Dest[i][j].y;
        }
        dr_total += drumuri;
    }

    printf("%d\n", dr_total);
}

int main()
{
    citire();
    rez();
    return 0;
}