問題概要

二次元平面上に $N$ 個の点があります。 $i$ 番目の点の座標を $(x_{i}, y_{i})$ とします。

この二次元平面上で各辺が X 軸・Y 軸に平行であるような長方形であって、 $N$ 個の点のうち $K$ 個以上の点を内部および周に含むようなものを考えます。

そのような長方形の面積の最小値を求めてください。

制約

$2 \le K \le N \le 50$

考えたこと

一見手のつけづらい問題だけど、この手の幾何の問題で考えるべきことは「ギリギリを考える」ということだ。

たとえばある長方形が、その内部に $K$ 個以上の点を含むとする。このとき、この長方形を少しずつ縮めて、それらの点がちょうど長方形の周上に引っかかるところまで縮めてもよいことがわかる。

このように考えると、次のことが言えるのだ。

長方形のうち、

左辺の X 座標が $x_{0}, \dots, x_{N-1}$ のいずれかに一致
右辺の X 座標が $x_{0}, \dots, x_{N-1}$ のいずれかに一致
上辺の Y 座標が $y_{0}, \dots, y_{N-1}$ のいずれかに一致
下辺の Y 座標が $y_{0}, \dots, y_{N-1}$ のいずれかに一致

という条件を満たすもののみを考えればよい。

計算量を評価しよう。

考慮すべき長方形の個数： $O(N^{4})$
各長方形に対して、内部に何個の点があるかの判定： $O(N)$

よって、全体として $O(N^{5})$ の計算量となる。

コード

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<long long> X(N), Y(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];

    long long res = 1LL<<62;
    for (int l = 0; l < N; ++l) {
        for (int r = 0; r < N; ++r) {
            long long L = X[l], R = X[r];
            for (int b = 0; b < N; ++b) {
                for (int t = 0; t < N; ++t) {
                    long long B = Y[b], T = Y[t];
                    int num = 0;
                    for (int i = 0; i < N; ++i) {
                        if (L <= X[i] && X[i] <= R &&
                            B <= Y[i] && Y[i] <= T) ++num;
                    }

                    if (num >= K) {
                        res = min(res, (R - L) * (T - B));
                    }
                }
            }
        }
    }
    cout << res << endl;
}