IOI Fever

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

// returns number of elements strictly smaller than v in vec
template<class T>
int bins(const vector<T>& vec, T v) {
    int low = 0;
    int high = vec.size();
    while(low != high) {
        int mid = (low + high) >> 1;
        if (vec[mid] < v) low = mid + 1;
        else high = mid;
    }
    return low;
}

// Struct for priority queue operations on index set [0, n-1]
// push(i, v) overwrites value at position i if one already exists
// decKey is faster but requires that the new key is smaller than the old one
struct Prique {
    const ll INF = (ll)1e18;
    vector<pair<ll, int>> data;
    const int n;

    Prique(int siz) : n(siz), data(2*siz, {INF, -1}) { data[0] = {-INF, -1}; }
    bool empty() const { return data[1].second >= INF; }
    pair<ll, int> top() const { return data[1]; }

    void push(int i, ll v) {
        data[i+n] = {v, (v >= INF ? -1 : i)};
        for (i += n; i > 1; i >>= 1) data[i>>1] = min(data[i], data[i^1]);
    }
    void decKey(int i, ll v) {
        for (int j = i+n; data[j].first > v; j >>= 1) data[j] = {v, i};
    }
    pair<ll, int> pop() {
        auto res = data[1];
        push(res.second, INF);
        return res;
    }
};

// Segment tree for range minimum and range capping
class SegTree {
    private:
        const ll INF = (ll)1e18;
        vector<ll> mn, cap, base;
        int h = 1;

        void apply(int i, ll v) {
            cap[i] = min(cap[i], v);
            mn[i] = min(mn[i], base[i] + cap[i]);
        }
        void push(int i) {
            apply(2*i, cap[i]);
            apply(2*i+1, cap[i]);
            cap[i] = INF;
        }

        void recApply(int a, int b, ll v, int i, int ia, int ib) {
            if (ib <= a || b <= ia) return;
            if (a <= ia && ib <= b) {
                apply(i, v);
            } else {
                push(i);
                int im = (ia + ib) >> 1;
                recApply(a, b, v, 2*i, ia, im);
                recApply(a, b, v, 2*i+1, im, ib);
                mn[i] = min(mn[2*i], mn[2*i+1]);
            }
        }
    public:
        SegTree(int n) {
            while(h < n) h *= 2;
            mn.resize(2*h, 2*INF); base.resize(2*h, INF); cap.resize(2*h, INF);
        }
        void rangeCap(int a, int b, ll v) { recApply(a, b+1, v, 1, 0, h); }
        ll getMinVal() { return mn[1]; }

        void setBase(int i, ll v) {
            i += h;
            base[i] = v;
            mn[i] = base[i] + cap[i];
            for (i >>= 1; i > 0; i >>= 1) {
                base[i] = min(base[2*i], base[2*i+1]);
                mn[i] = min(cap[i] + base[i], min(mn[2*i], mn[2*i+1]));
            }
        }

        pair<ll, int> getMin() {
            int i = 1;
            ll res = mn[1];
            while(i < h) {
                push(i);
                if (mn[2*i] == mn[i]) i = 2*i;
                else i = 2*i+1;
            }
            return {res, i - h};
        }
};

pair<int, int> rotate(pair<int, int> dir) {
    return {dir.second, -dir.first};
}
int sign(ll v) {
    return (v < 0 ? -1 : v > 0);
}

int solve(const vector<pair<ll, ll>>& pts) {
    int n = pts.size();
    vector<int> dir(n); // RIGHT DOWN LEFT UP
    dir[0] = 0;
    for (int i = 1; i < n; ++i) {
        ll dx = pts[i].first, dy = pts[i].second;
        if (abs(dx) > abs(dy)) {
            if (dx < 0) dir[i] = 0;
            else dir[i] = 2;
        } else if (abs(dy) > abs(dx) || dx > 0) {
            if (dy < 0) dir[i] = 3;
            else dir[i] = 1;
        } else {
            dir[i] = 0;
        }
    }

    vector<pair<int, int>> diffs(8);
    diffs[0] = {1, 0};
    diffs[1] = {1, -1};
    diffs[2] = {0, -1};
    diffs[3] = {-1, -1};
    diffs[4] = {-1, 0};
    diffs[5] = {-1, 1};
    diffs[6] = {0, 1};
    diffs[7] = {1, 1};

    vector<vector<array<ll, 4>>> ords(8);
    for (int i = 0; i < n; ++i) {
        int dx = sign(diffs[2*dir[i]].first);
        int dy = sign(diffs[2*dir[i]].second);
        for (int j = 0; j < 8; ++j) {
            if (sign(diffs[j].first) != -dx && sign(diffs[j].second) != -dy) continue;
            array<ll, 4> off;
            off[0] = dir[i];

            pair<int, int> tar = diffs[j];
            pair<int, int> ortho = rotate(tar);
            off[1] = ortho.first * pts[i].first + ortho.second * pts[i].second;
            off[2] = tar.first * pts[i].first + tar.second * pts[i].second;
            off[3] = i;

            ords[j].push_back(off);
        }
    }
    for (int j = 0; j < 8; ++j) sort(ords[j].begin(), ords[j].end());

    vector<SegTree> segs;
    for (int j = 0; j < 8; ++j) {
        segs.emplace_back(ords[j].size());
        for (int i = 0; i < ords[j].size(); ++i) {
            if (ords[j][i][3] == 0) {
                segs[j].setBase(i, 0);
                segs[j].rangeCap(i, i, 0);
            } else {
                segs[j].setBase(i, ords[j][i][2]);
            }
        }
    }

    Prique pq(8);
    for (int j = 0; j < 8; ++j) pq.decKey(j, segs[j].getMin().first);

    vector<ll> times(n, INF);

    for (int j = pq.pop().second; j != -1; j = pq.pop().second) {
        auto opt = segs[j].getMin();
        segs[j].setBase(opt.second, INF);
        pq.decKey(j, segs[j].getMinVal());

        int i = ords[j][opt.second][3];
        ll t = opt.first;

        if (t >= INF / 2) break;
        if (t >= times[i]) continue;
        times[i] = t;

        int d = dir[i];
        for (int j2 = 0; j2 < 8; ++j2) {
            array<ll, 4> ind;

            // Desired direction
            if (j2 == (2*d+7) % 8) ind[0] = (d+1) % 4;
            else if (j2 == 2*d) ind[0] = (d + 2) % 4;
            else if (j2 == (2*d+1) % 8) ind[0] = (d+3) % 4;
            else continue;

            // Desired line
            pair<int, int> ortho = rotate(diffs[j2]);
            ind[1] = ortho.first * pts[i].first + ortho.second * pts[i].second;

            // Desired min coordinate
            ll base = diffs[j2].first * pts[i].first + diffs[j2].second * pts[i].second;
            ind[2] = t + base;

            // OK indices
            ind[3] = -1;

            int i0 = bins(ords[j2], ind);

            ind[2] = INF;

            int i1 = bins(ords[j2], ind);

            segs[j2].rangeCap(i0, i1 - 1, -base);
            pq.decKey(j2, segs[j2].getMinVal());
        }
    }

    int res = 0;
    for (ll& v : times) res += (v < INF);
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<pair<ll, ll>> pts(n);
    for (int i = 0; i < n; ++i) {
        int y, x;
        cin >> y >> x;
        pts[i] = {y, x};
    }
    for (int i = 1; i < n; ++i) {
        pts[i].first -= pts[0].first;
        pts[i].second -= pts[0].second;
    }
    pts[0] = {0, 0};

    // Decide direction person 1 goes to
    int res = 0;
    res = max(res, solve(pts)); // Right
    for (auto& pr : pts) pr.first = -pr.first;
    res = max(res, solve(pts)); // Left
    for (auto& pr : pts) swap(pr.first, pr.second);
    res = max(res, solve(pts)); // Up
    for (auto& pr : pts) pr.first = -pr.first;
    res = max(res, solve(pts)); // Down

    cout << res << '\n';
}