Cod sursa(job #6546)

Utilizator dominoMircea Pasoi domino Data 20 ianuarie 2007 00:48:19
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 50005
#define FIN "pachete.in"
#define FOUT "pachete.out"
#define FOR(i, a, b) for (i = (a); i < (b); i++)
#define mp make_pair
#define f first
#define s second

int N, Ox, Oy, V[MAX_N], nv, Res;
pair<int, pair<int, int> > P[MAX_N];

int main(void)
{
    int i, x, y, pos;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d", &N);
    scanf("%d %d", &Ox, &Oy);
    FOR (i, 0, N)
    {
        scanf("%d %d", &x, &y);
        x -= Ox; y -= Oy;
        if (x < 0 && y < 0) 
            P[i] = mp(2, mp(-x, -y));
        else
        if (y < 0)
            P[i] = mp(3, mp(x, -y));
        else
        if (x < 0)
            P[i] = mp(1, mp(-x, y));
        else
            P[i] = mp(0, mp(x, y));
    }   

    sort(P, P+N);
    FOR (i, 0, N)
    {
        if (i > 0 && P[i].f != P[i-1].f) { Res += nv; nv = 0; }
        pos = lower_bound(V, V+nv, -P[i].s.s)-V;
        V[pos] = -P[i].s.s;
        if (pos == nv) nv++;
    }
    Res += nv;

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

    return 0;
}