解法

概要

\(f(3) \le f(4) = f(5) = f(6) = \dots\)。 \(O(n)\)。

詳細

\(k \ge 4\) について \(f(k) = 2 \cdot (\max x_i - \min x_i) + 2 \cdot (\max y_i - \min y_i)\) なのは明らか。 \(f(3)\) の場合だけが問題だが、\(1\)点を固定したとき残りの\(2\)点は \(\max x_i, \min x_i, \max y_i, \min y_i\) を達成する点から選ぶとしても全体の最大値は変わらない。 よって \(O(n)\) で解ける。

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <class T, class U> inline void chmax(T & a, U const & b) { a = max<T>(a, b); }

vector<ll> solve(int n, vector<ll> const & x, vector<ll> const & y) {
    ll min_x = *min_element(ALL(x));
    ll max_x = *max_element(ALL(x));
    ll min_y = *min_element(ALL(y));
    ll max_y = *max_element(ALL(y));

    ll f3 = 0;
    REP (i, n) {
        ll w = max(max_x - x[i], x[i] - min_x);
        ll h = max(max_y - y[i], y[i] - min_y);
        chmax(f3, 2 * w + 2 * h);
    }
    ll f4 = 2 * (max_x - min_x) + 2 * (max_y - min_y);

    vector<ll> f(n - 2, f4);
    f[0] = f3;
    return f;
}

int main() {
    int n; scanf("%d", &n);
    vector<ll> x(n), y(n);
    REP (i, n) {
        scanf("%lld%lld", &x[i], &y[i]);
    }
    vector<ll> f = solve(n, x, y);
    REP (k, n - 2) {
        printf("%lld%c", f[k], k + 1 < n - 2 ? ' ' : '\n');
    }
    return 0;
}