Cod sursa(job #1503757)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 16 octombrie 2015 21:40:26
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#include <algorithm>

#define DIM 51000
#define f first
#define s second
using namespace std;

int N, X, Y, nr, xSt, ySt, D[DIM];
pair <int, int> List1[DIM];
pair <int, int> List2[DIM];
pair <int, int> List3[DIM];
pair <int, int> List4[DIM];

void runAlgorithm (pair <int, int> Vector[])
{
    sort (Vector + 1, Vector + Vector[0].f + 1);
    if (Vector[0].f == 0) return; int nr2 = 1;

    D[1] = Vector[1].s;
    for (int i = 2; i <= Vector[0].f; i ++)
    {
        int st = 1, dr = nr2, mid;

        while (st <= dr)
        {
            mid = st + ((dr - st) >> 1);

            if (Vector[i].s < D[mid])
                st = mid + 1;
            else
                dr = mid - 1;
        }

        if (dr == nr2)
            D[++nr2] = Vector[i].s;
        else
            D[st] = Vector[i].s;
    }

    nr += nr2;

    return;
}

int main ()
{
    freopen ("pachete.in" ,"r", stdin );
    freopen ("pachete.out","w", stdout);

    scanf ("%d", &N);
    scanf ("%d %d", &xSt, &ySt);

    for (int i = 1; i <= N; i ++)
    {
        scanf ("%d %d", &X, &Y);
        X -= xSt;
        Y -= ySt;

        if (X <  0 && Y <  0) List1[++List1[0].f] = make_pair(-X, -Y); else
        if (X <  0 && Y >= 0) List2[++List2[0].f] = make_pair(-X, +Y); else
        if (X >= 0 && Y <  0) List3[++List3[0].f] = make_pair(+X, -Y); else
        if (X >= 0 && Y >= 0) List4[++List4[0].f] = make_pair(+X, +Y); else
                printf ("Coordonatele sunt prea complexe!");
    }

    runAlgorithm (List1); runAlgorithm (List2);
    runAlgorithm (List3); runAlgorithm (List4);

    printf ("%d\n", nr);

    fclose (stdin );
    fclose (stdout);

    return 0;
}