Codeforces Round #500 (Div. 1) [based on EJOI]: A. Photo of The Sky
problem
長さ $2n$ の数列 $a$ が与えられる。 その要素を $a = x \cup y$ と $n$ 個ずつに分割したときの $(\max y - \min y) (\max x - \min x)$ の最小値を求めよ。
solution
$a$ を整列し、その長さ $n$ の区間を $y$、残りを $x$ とする。 これを全ての可能な $y$ について試す。 $O(n \log n)$。
note
前半分と後ろ半分に分けるだけでしょ、をやって1WAした
implementation
#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> inline void chmin(T & a, T const & b) { a = min(a, b); }
int main() {
// input
int n; scanf("%d", &n);
vector<int> a(2 * n);
REP (i, 2 * n) scanf("%d", &a[i]);
// solve
sort(ALL(a));
ll ans = LLONG_MAX;
REP (l, n + 1) {
int r = l + n - 1;
ll h = a[r] - a[l];
ll w = a[2 * n - 1] - a[0];
chmin(ans, h * w);
}
ll h = a[ n - 1] - a[0];
ll w = a[2 * n - 1] - a[n];
chmin(ans, h * w);
// output
cout << ans << endl;
return 0;
}