Cod sursa(job #2551576)

Utilizator bluestorm57Vasile T bluestorm57 Data 19 februarie 2020 22:36:03
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 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;
vector < pair < int, int > > v1, v2, v3, v4;

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(vector < pair < int, int > > v){
    if(v.empty()) return 0;

    sort(v.begin(), v.end(), cmp);

    vector < int > work; /// that's a vector that help us to solve
    ///previous comment was special for my infoarena friend
    work.push_back(0); /// this is for nothing
    int lo, hi, mid, ans = 0, n = 0;

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

        if(lo == n + 1){
            work.push_back(it.second);
            n++;
            ans++;
        }else
            work[lo] = it.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){
            if(v[i].se >= 0)
                v1.push_back(v[i]);
            else
                v4.push_back(v[i]);
        }else{
            if(v[i].se >= 0)
                v2.push_back(v[i]);
            else
                v3.push_back(v[i]);
        }
    }

    ans += solve(v1);
    ans += solve(v2);
    ans += solve(v3);
    ans += solve(v4);

    g << ans;

    return 0;
}