Submission #6188680

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }
template <class T, class U> inline void chmax(T & a, U const & b) { a = max<T>(a, b); }

template <typename UnaryPredicate>
int64_t binsearch(int64_t l, int64_t r, UnaryPredicate p) {
    assert (l <= r);
    -- l;
    while (r - l > 1) {
        int64_t m = l + (r - l) / 2;
        (p(m) ? r : l) = m;
    }
    return r;
}


struct desc_t {
    array<ll, 2> incr, decr, fixed;
};

desc_t describe(int n, const vector<ll> & x, const vector<char> & d, char incr, char decr) {
    desc_t a = {
        {{ LLONG_MAX / 3, LLONG_MIN / 3 }},
        {{ LLONG_MAX / 3, LLONG_MIN / 3 }},
        {{ LLONG_MAX / 3, LLONG_MIN / 3 }},
    };
    REP (i, n) {
        if (d[i] == incr) {
            chmin(a.incr[0], x[i]);
            chmax(a.incr[1], x[i]);
        } else if (d[i] == decr) {
            chmin(a.decr[0], x[i]);
            chmax(a.decr[1], x[i]);
        } else {
            chmin(a.fixed[0], x[i]);
            chmax(a.fixed[1], x[i]);
        }
    }
    return a;
}

ll get_doubled_length(const desc_t & a, ll t2) {
    ll l = min(2 * a.incr[0] + t2, min(2 * a.decr[0] - t2, 2 * a.fixed[0]));
    ll r = max(2 * a.incr[1] + t2, max(2 * a.decr[1] - t2, 2 * a.fixed[1]));
    return r - l;
}

long double get_area(const desc_t & ax, const desc_t & ay, ll t2) {
    return get_doubled_length(ax, t2) * get_doubled_length(ay, t2) / 4.l;
}

vector<ll> list_boundaries(const desc_t & a) {
    constexpr ll limit = 1e9;
    vector<ll> b;
    b.push_back(0);
    while (b.back() != limit) {
        ll l = b.back();
        ll c = get_doubled_length(a, l);
        ll d = get_doubled_length(a, l + 1) - get_doubled_length(a, l);
        ll r = binsearch(l, limit, [&](ll t) {
            return get_doubled_length(a, t) != c + d * (t - l);
        });
        b.push_back(r);
    }
    return b;
}

long double solve(int n, const vector<ll> & x, const vector<ll> & y, const vector<char> & d) {
    desc_t ax = describe(n, x, d, 'R', 'L');
    desc_t ay = describe(n, y, d, 'U', 'D');

    vector<ll> bx = list_boundaries(ax);
    vector<ll> by = list_boundaries(ay);
    vector<ll> b;
    copy(ALL(bx), back_inserter(b));
    copy(ALL(by), back_inserter(b));
    sort(ALL(b));
    b.erase(unique(ALL(b)), b.end());

    long double ans = INFINITY;
    REP (i, b.size() - 1) {
        ll l = b[i];
        ll r = b[i + 1];
        chmin(ans, get_area(ax, ay, l));
        chmin(ans, get_area(ax, ay, r));
        binsearch(l, r, [&](ll t) {
            chmin(ans, get_area(ax, ay, t));
            chmin(ans, get_area(ax, ay, t + 1));
            return get_area(ax, ay, t + 1) >= get_area(ax, ay, t);
        });
    }
    return ans;
}

int main() {
    int n; cin >> n;
    vector<ll> x(n), y(n);
    vector<char> d(n);
    REP (i, n) {
        cin >> x[i] >> y[i] >> d[i];
    }
    cout << setprecision(18) << solve(n, x, y, d) << endl;
    return 0;
}

Submission Info

Judge Result