AOJ 0302 Star Watching
解法
星を輝度でソートする.
輝度の最小(つまり左端)を決めて,しゃくとり法でできる.
座標の最大最小は,priority_queueでもmapでもmultisetでもなんでもよい.
自分は最初 priority_queue で書いて通したが,他の人のコードを読むと multiset が一番すっきりしていたのでそちらで書き直した.
計算量は O(NlogN)
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { int N, d; cin >> N >> d; vector<tuple<int, ll, ll>> v(N); for(int i=0; i<N; ++i) { int b; ll x, y; cin >> x >> y >> b; v[i] = make_tuple(b, x, y); } sort(v.begin(), v.end()); ll res = 0; multiset<ll> x, y; int r = 0; for(int l=0; l<N; ++l) { while(r < N && get<0>(v[r]) - get<0>(v[l]) <= d) { x.insert(get<1>(v[r])); y.insert(get<2>(v[r])); r++; } res = max(res, (*x.rbegin() - *x.begin()) * (*y.rbegin() - *y.begin())); if(r == N) { break; } x.erase(x.find(get<1>(v[l]))); y.erase(y.find(get<2>(v[l]))); } cout << res << endl; }