Cod sursa(job #594127)

Utilizator SpiderManSimoiu Robert SpiderMan Data 6 iunie 2011 13:27:37
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
# include <algorithm>
# include <cstdio>
using namespace std;

# define mp make_pair
# define x first
# define y second

typedef pair <int, int> PR ;
const char *FIN = "pachete.in", *FOU = "pachete.out" ;
const int MAX = 50005;

pair <int, PR> punct[MAX];
PR O ;
int N, sol, cnt, V[MAX] ;

pair <int, PR> caz (PR C) {
    if (C.x < 0 && C.y < 0) {
        return mp (2, mp (-C.x, -C.y)) ;
    } else if (C.y < 0) {
        return mp (3, mp (C.x, -C.y)) ;
    } else if (C.x < 0) {
        return mp (1, mp (-C.x, C.y)) ;
    } else {
        return mp (0, C) ;
    }
}

int main (void) {
    freopen (FIN, "r", stdin) ;

    scanf ("%d %d %d", &N, &O.x, &O.y) ;
    for (int i = 0, x, y; i < N; ++i) {
        scanf ("%d %d", &x, &y) ;
        punct[i] = caz (mp (x - O.x, y - O.y)) ;
    }
    sort (punct, punct + N) ;
    for (int i = 0; i < N; ++i) {
        if (i > 0 && punct[i].x != punct[i - 1].x)
            sol += cnt, cnt = 0;
        int aux = lower_bound (V, V + cnt, -punct[i].y.y) - V;
        V[aux] = -punct[i].y.y;
        if (aux == cnt) ++cnt;
    }
    fprintf (fopen (FOU, "w"), "%d", cnt + sol) ;
}