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;
}