Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1): C. Optimal Polygon Perimeter
解法
概要
\(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;
}