Cod sursa(job #8005)

Utilizator astronomyAirinei Adrian astronomy Data 23 ianuarie 2007 16:25:20
Problema Pachete Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN (1 << 16)
#define abs(x) ((x) < 0 ? (-(x)) : (x))

typedef struct point { int x, y; } point;

int N, V[MAXN], res, xs, ys;
int Na, Nb, Nc, Nd;
point A[MAXN], B[MAXN], C[MAXN], D[MAXN];

int cmp(const void *a, const void *b)
{
    return ((point*)a)->x - ((point*)b)->x;
}

int baga(point A[MAXN], int N)
{
    int i, Nr, st, dr, m, r;

    if(N == 0)
        return 0;
        
    qsort(A+1, N, sizeof(A[0]), cmp);
    
    V[Nr = 1] = A[1].y;

    for(i = 2; i <= N; i++)
    {
        if(A[i].y < V[Nr])
            V[++Nr] = A[i].y;
        else
        {
            st = 1, dr = Nr;
            while(st <= dr)
            {
                m = (st+dr) >> 1;
                if(A[i].y > V[m])
                    r = m, dr = m-1;
                else
                    st = m+1;
            }
            V[r] = A[i].y;
        }
    }

    return Nr;
}

void read_and_solve(void)
{
    int i, x, y;

    scanf("%d\n", &N);
    scanf("%d %d\n", &xs, &ys);

    for(i = 1; i <= N; i++)
    {
        scanf("%d %d\n", &x, &y);
        if(x < xs && y > ys)
            A[++Na].x = x, A[Na].y = y;
        if(x < xs && y < ys)
            D[++Nd].x = x, D[Nd].y = y;
        if(x > xs && y > ys)
            B[++Nb].x = x, B[Nb].y = y;
        if(x > xs && y < ys)
            C[++Nc].x = x, C[Nc].y = y;
    }

    res += baga(B, Nb);
    
    for(i = 1; i <= Na; i++)
    {
        x = A[i].x, y = A[i].y;
        A[i].x = y, A[i].y = abs(x);
    }
    res += baga(A, Na);

    for(i = 1; i <= Nc; i++)
    {
        x = C[i].x, y = C[i].y;
        C[i].x = abs(y), C[i].y = x;
    }
    res += baga(C, Nc);

    for(i = 1; i <= Nd; i++)
    {
        x = D[i].x, y = D[i].y;
        D[i].x = abs(x), D[i].y = abs(y);
    }
    res += baga(D, Nd);

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

int main(void)
{
    freopen("pachete.in", "rt", stdin);
    freopen("pachete.out", "wt", stdout);

    read_and_solve();

    return 0;
}