算法
(暴力枚举) $O(N^5)$
这里数据比较小,所以暴力枚举即可
枚举矩形的左上顶点和右下顶点就能确定一个矩形
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
inline void chmax(ll& x, ll y) { if (x > y) x = y; }
int main() {
int n, k;
cin >> n >> k;
vector<int> x(n), y(n);
rep(i, n) cin >> x[i] >> y[i];
vector<int> nx = x;
vector<int> ny = y;
sort(nx.begin(), nx.end());
sort(ny.begin(), ny.end());
ll ans = 4e18;
rep(l, n) {
for (int r = l+1; r < n; ++r) {
rep(d, n) {
for (int u = d+1; u < n; ++u) {
int cnt = 0;
rep(i, n) {
if (nx[l] <= x[i] and x[i] <= nx[r] and ny[d] <= y[i] and y[i] <= ny[u]) {
cnt++;
}
}
if (cnt >= k) {
chmax(ans, ll(nx[r]-nx[l])*(ny[u]-ny[d]));
}
}
}
}
}
cout << ans << '\n';
return 0;
}