Cod sursa(job #1434882)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 11 mai 2015 16:43:13
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define x first
#define y second
#define NMAX 50007

using namespace std;

int n, X, Y, Ans, Dp[NMAX];
vector < pair < int, int > > v[5];

int cb(vector < pair < int, int > > v){
    Dp[0] = 0;
    for(int i = 0; i < v.size(); ++i){
        int st = 1, dr = Dp[0], med, w = 1;
        while (st <= dr){
            med = (st + dr) >> 1;
            if(Dp[med] <= v[i].y) {
                w = 0;
                dr = med - 1;
            }
            else
                st = med + 1;
        }
        if(w)
            Dp[++Dp[0]] = v[i].y;
        else
            Dp[st] = v[i].y;
    }
    return Dp[0];
}

int main(){
    freopen("pachete.in", "r", stdin);
    freopen("pachete.out", "w", stdout);
    scanf("%d", &n);
    scanf("%d %d", &X, &Y);
    for (int i = 1; i <= n; ++i){
        int a, b;
        scanf("%d %d", &a, &b);
        a -= X;
        b -= Y;
        if(a > 0 && b > 0)
            v[1].push_back(make_pair(a, b));
        if(a > 0 && b < 0)
            v[2].push_back(make_pair(a, -b));
        if(a < 0 && b < 0)
            v[3].push_back(make_pair(-a, -b));
        if(a < 0 && b > 0)
            v[4].push_back(make_pair(-a, b));
    }
    for (int i = 1; i <= 4; ++i){
        sort(v[i].begin(), v[i].end());
        Ans += cb(v[i]);
    }
    printf("%d\n", Ans);
    return 0;
}