Stock Trading

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const long long INF = 1e17; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0); 
    9    int n; cin >> n;
    10    vector<pair<ll, ll>> v;
    11    for (int i = 0; i < n; i++) {
    12        ll x, y; cin >> x >> y;
    13        v.emplace_back(x, y);
    14    }
    15    ll cnt = 0;
    16    sort(v.begin(), v.end());
    17    auto slope_less = [&](int i, int a, int b) { // slope(i,a) <= slope(i,b)
    18        i128 lhs = (i128)(v[a].second - v[i].second) * (v[b].first - v[i].first);
    19        i128 rhs = (i128)(v[b].second - v[i].second) * (v[a].first - v[i].first);
    20        return lhs <= rhs;
    21    };
    22    auto slope_greater = [&](int i, int a, int b) { // slope(i,a) >= slope(i,b)
    23        i128 lhs = (i128)(v[a].second - v[i].second) * (v[b].first - v[i].first);
    24        i128 rhs = (i128)(v[b].second - v[i].second) * (v[a].first - v[i].first);
    25        return lhs >= rhs;
    26    };
    27    for (int i = 0; i < n; i++) {
    28        int mn = -1, mx = -1;
    29        for (int j = i + 1; j < n; j++) {
    30            bool flag = 1;
    31            if (mn != -1) {
    32                if (!(slope_less(i, j, mn) || slope_greater(i, j, mx))) flag = 0;
    33            }
    34            if (flag) cnt++;
    35            if (mn == -1) {
    36                mn = mx = j;
    37            } else {
    38                if (slope_less(i, j, mn)) mn = j;
    39                if (slope_greater(i, j, mx)) mx = j;
    40            }
    41        }
    42    }
    43    cout << cnt << '\n';
    44    return 0;
    45}