Cod sursa(job #2552073)

Utilizator bluestorm57Vasile T bluestorm57 Data 20 februarie 2020 15:51:44
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

ifstream f("pachete.in");
ofstream g("pachete.out");

const int NMAX = 50005;
int n;
long long ans;
pair < int, int > v[NMAX],start;
pair < int, int > v1[NMAX], v2[NMAX], v3[NMAX], v4[NMAX];
int elem1, elem2, elem3, elem4, work[NMAX];

bool cmp(const pair < int, int > &X, const pair < int, int > &Y){
    if(X.fi != Y.fi)
        return X.fi < Y.fi;
    return X.se < Y.se;
}

int solve(pair < int, int > v[], int n){
    if(n == 0) return 0;

    sort(v + 1, v + n + 1);

    /// that's a vector that help us to solve: work
    ///previous comment was special for my infoarena friend

    int lo, hi, mid, ans = 0, elem = 0;

    for(int i = 1 ; i <= n ; i++){
        lo = 1;
        hi = elem;
        while(lo <= hi){
            mid = (lo + hi) / 2;
            if(work[mid] < v[i].second)
                hi = mid - 1;
            else
                lo = mid + 1;
        }

        if(lo == elem + 1){
            work[++elem] = v[i].second;
            ans++;
        }else
            work[lo] = v[i].second;
    }

    return ans;
}

int main(){
    int i;
    f >> n >> start.fi >> start.se;
    for(i = 1 ; i <= n ; i++){
        f >> v[i].fi >> v[i].se;
        v[i].fi -= start.fi;
        v[i].se -= start.se;

        if(v[i].fi == 0 || v[i].se == 0)
            continue;

        if(v[i].fi < 0){
            if(v[i].se >= 0)
                v1[++elem1] = v[i];
            else
                v4[++elem4] = v[i];
        }else{
            if(v[i].se >= 0)
                v2[++elem2] = v[i];
            else
                v3[++elem3] = v[i];
        }
    }

    ans += solve(v1, elem1);
    ans += solve(v2, elem2);
    ans += solve(v3, elem3);
    ans += solve(v4, elem4);

    g << ans;

    return 0;
}