ABC075D
解法
制約より、各座標のX軸・Y軸の値は異なるので、各座標をX軸の値によってソートすると、求める長方形のX軸の長さは、のいずれかである。
あとは、これらの範囲において、Y軸の長さが最小になるように5個選ぶことを考えれば良い。これは、範囲内の座標をY軸の値によってソートすることで簡単に求められる。
計算量はとなり、なので十分間に合う。
コード
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; typedef pair<ll, ll> P; int main() { int N, K; cin >> N >> K; vector<P> v(N); for (int i = 0; i < N; i++) { ll x, y; cin >> x >> y; v[i] = P(x, y); } sort(v.begin(), v.end(), [](P a, P b) { return a.first < b.first; }); ll ans = -1; for (int l = 0; l < N-K+1; l++) { for (int r = l+K-1; r < N; r++) { vector<P> v2(r-l+1); copy(v.begin()+l, v.begin()+r+1, v2.begin()); sort(v2.begin(), v2.end(), [](P a, P b) { return a.second < b.second; }); ll dx = v[r].first - v[l].first; for (int i = 0; i < v2.size()-K+1; i++) { ll dy = v2[K-1+i].second - v2[i].second; ll area = dx * dy; ans = ans < 0 ? area : min(ans, area); } } } cout << ans << endl; }
一言
Y軸の値を小さいほうから5個選んでしまっていたため、WAを出してしまった。
(結構悩んだ)