AOJ 0302: 天体観測/Star Watching

目に入ったので解いた。あまり難しくない。

solution

しゃくとり法。$O(N\log N)$。

最も明るい星について全部試す。その星より$d$まで暗い星をしゃくとり法で集めてきて、ordered setあたりで各座標軸ごとの最大最小を取る。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
typedef long long ll;
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
struct star_t { int x, y, b; };
bool operator < (star_t p, star_t q) { return p.b < q.b; }
int main() {
    int n, d; scanf("%d%d", &n, &d);
    vector<star_t> s(n); repeat (i,n) scanf("%d%d%d", &s[i].x, &s[i].y, &s[i].b);
    whole(sort, s);
    ll ans = 0;
    map<int, int> x, y;
    for (int i = 0, j = 0; j < n; ++ j) {
        x[s[j].x] += 1;
        y[s[j].y] += 1;
        while (s[i].b + d < s[j].b) {
            x[s[i].x] -= 1; if (not x[s[i].x]) x.erase(s[i].x);
            y[s[i].y] -= 1; if (not y[s[i].y]) y.erase(s[i].y);
            ++ i;
        }
        ll dx = x.rbegin()->first - x.begin()->first;
        ll dy = y.rbegin()->first - y.begin()->first;
        setmax(ans, dx * dy);
    }
    printf("%lld\n", ans);
    return 0;
}