Axis-Parallel Rectangle [AtCoder Beginner Contest 075 D]

https://beta.atcoder.jp/contests/abc075/tasks/abc075_d

解法

https://beta.atcoder.jp/contests/abc075/submissions/1682970

まず重要な考察がある。
「最適な長方形は四辺がどれも何かの頂点と交わっている」
仮に頂点がK個以上あり、四辺のうちどこかが何かの頂点と交わっていない長方形があった場合、交わっていない辺を移動させて、より面積が小さい長方形に変形できるためである。
　
長方形の上下左右を全探索するが、その候補は頂点のx,y座標に限られる。
この候補から、長方形の左下を(sx,sy), 右上を(tx,ty)として全探索しよう。
選んだ長方形の中に何個の頂点が含まれるかも愚直に全てチェックしていけばいい。
個数がK個以上なら最小値を更新していって答える。

typedef long long ll;
int N, K;
ll X[101], Y[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> X[i] >> Y[i];
 
    set<int> xx, yy;
    rep(i, 0, N) xx.insert(X[i]);
    rep(i, 0, N) yy.insert(Y[i]);
 
    ll ans = -1;
    fore(sx, xx) fore(sy, yy) fore(tx, xx) fore(ty, yy) if (sx <= tx and sy <= ty) {
        ll sm = 1LL * (tx - sx) * (ty - sy);
 
        int c = 0;
        rep(i, 0, N) if (sx <= X[i] and X[i] <= tx and sy <= Y[i] and Y[i] <= ty) c++;
        if (K <= c) {
            if (ans < 0) ans = sm;
            ans = min(ans, sm);
            
        }
    }
    cout << ans << endl;
}