Language: C++

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define ALL(name) name.begin(),name.end()
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

ll N;
vector<double> X, Y;
vector<char> D;

// 移動開始 m 秒後の Ymax/Xmax を求めます O(N)
// isX が true なら Xmax を、そうでなければ Ymax を返します
double GetMax(double m, bool isX) {
    double ret = -DINF;
    REP(i, N) {
        double cur = (isX) ? X[i] : Y[i];
        if(isX) {
            if(D[i] == 'R') { cur += m; }
            else if(D[i] == 'L') { cur -= m; }
        }
        else {
            if(D[i] == 'U') { cur += m; }
            else if(D[i] == 'D') { cur -= m; }
        }
        ret = max(ret, cur);
    }
    return ret;
}
// 移動開始 m 秒後の Ymin/Xmin を求めます O(N)
// isX が true なら Xmin を、そうでなければ Ymin を返します
double GetMin(double m, bool isX) {
    double ret = DINF;
    REP(i, N) {
        double cur = (isX) ? X[i] : Y[i];
        if(isX) {
            if(D[i] == 'R') { cur += m; }
            else if(D[i] == 'L') { cur -= m; }
        }
        else {
            if(D[i] == 'U') { cur += m; }
            else if(D[i] == 'D') { cur -= m; }
        }
        ret = min(ret, cur);
    }
    return ret;
}

// 移動開始 m 秒後の (Xmax - Xmin) * (Ymax - Ymin) を求めます O(N)
double GetArea(double m) {
    double x_max = -DINF;
    double x_min = DINF;
    double y_max = -DINF;
    double y_min = DINF;
    REP(i, N) {
        double cur_x = X[i];
        double cur_y = Y[i];
        if(D[i] == 'U') { cur_y += m; }
        else if(D[i] == 'D') { cur_y -= m; }
        else if(D[i] == 'R') { cur_x += m; }
        else if(D[i] == 'L') { cur_x -= m; }
        x_max = max(x_max, cur_x);
        x_min = min(x_min, cur_x);
        y_max = max(y_max, cur_y);
        y_min = min(y_min, cur_y);
    }
    return (x_max - x_min) * (y_max - y_min);
}

// Ymax/Xmax の減少が止まる（変わらなくなる）位置を求めます
// isX が true なら Xmax の位置を、そうでなければ Ymax の位置を返します
ll TriSearchMax1(bool isX) {
    ll lb = 1, ub = 200000000;
    while(ub - lb > 1) {
        ll mid = (lb + ub) / 2;
        double val_mid = GetMax(static_cast<double>(mid), isX);
        double val_prev = GetMax(static_cast<double>(mid - 1), isX);
        double val_next = GetMax(static_cast<double>(mid + 1), isX);
        if(val_prev < val_mid && val_mid < val_next)        { ub = mid; }
        else if(val_prev == val_mid && val_mid < val_next)  { ub = mid; }
        else if(val_prev == val_mid && val_mid == val_next) { ub = mid; }
        else if(val_prev > val_mid && val_mid == val_next)  { lb = mid; rb = mid + 1; break; }
        else if(val_prev > val_mid && val_mid > val_next)   { lb = mid; }
        else if(val_prev > val_mid && val_mid < val_next)   { lb = mid; rb = mid + 1; break; }
    }
    // この時点で lb + 1 = ub
    // lb から 0.5 刻みでチェックして厳密な位置を探る
    double mid = static_cast<double>(lb) - 0.5;
    double val_prev = GetMax(mid);
    REP(i, 4) {
        mid += 0.5;
        double val = GetMax(mid);
        if(val_prev <= val) { return mid - 0.5; }
        val_prev = val;
    }

    return mid;
}

// Ymax/Xmax が増加し始める位置を求めます
// isX が true なら Xmax の位置を、そうでなければ Ymax の位置を返します
ll TriSearchMax2(bool isX) {
    ll lb = 1, ub = 200000000;
    while(ub - lb > 1) {
        ll mid = (lb + ub) / 2;
        double val_mid = GetMax(static_cast<double>(mid), isX);
        double val_prev = GetMax(static_cast<double>(mid - 1), isX);
        double val_next = GetMax(static_cast<double>(mid + 1), isX);
        if(val_prev < val_mid && val_mid < val_next)        { lb = mid; }
        else if(val_prev == val_mid && val_mid < val_next)  { lb = mid; rb = mid + 1; break; }
        else if(val_prev == val_mid && val_mid == val_next) { lb = mid; }
        else if(val_prev > val_mid && val_mid == val_next)  { ub = mid; }
        else if(val_prev > val_mid && val_mid > val_next)   { ub = mid; }
        else if(val_prev > val_mid && val_mid < val_next)   { lb = mid; rb = mid + 1; break; }
    }
    // この時点で lb + 1 = ub
    // lb から 0.5 刻みでチェックして厳密な位置を探る
    double mid = static_cast<double>(lb) - 0.5;
    double val_prev = GetMax(mid);
    REP(i, 4) {
        mid += 0.5;
        double val = GetMax(mid);
        if(val_prev < val) { return mid - 0.5; }
        val_prev = val;
    }

    return mid;
}

// Ymin/Xmin の増加が止まる（変わらなくなる）位置を求めます
// isX が true なら Xmin の位置を、そうでなければ Ymin の位置を返します
ll TriSearchMin1(bool isX) {
    ll lb = 1, ub = 200000000;
    while(ub - lb > 1) {
        ll mid = (lb + ub) / 2;
        double val_mid = GetMin(static_cast<double>(mid), isX);
        double val_prev = GetMin(static_cast<double>(mid - 1), isX);
        double val_next = GetMin(static_cast<double>(mid + 1), isX);
        if(val_prev < val_mid && val_mid < val_next)        { lb = mid; }
        else if(val_prev == val_mid && val_mid < val_next)  { lb = mid; rb = mid + 1; break; }
        else if(val_prev == val_mid && val_mid == val_next) { lb = mid; }
        else if(val_prev > val_mid && val_mid == val_next)  { ub = mid; }
        else if(val_prev > val_mid && val_mid > val_next)   { ub = mid; }
        else if(val_prev > val_mid && val_mid < val_next)   { lb = mid; rb = mid + 1; break; }
    }
    // この時点で lb + 1 = ub
    // lb から 0.5 刻みでチェックして厳密な位置を探る
    double mid = static_cast<double>(lb) - 0.5;
    double val_prev = GetMin(mid);
    REP(i, 4) {
        mid += 0.5;
        double val = GetMin(mid);
        if(val_prev < val) { return mid - 0.5; }
        val_prev = val;
    }

    return mid;
}

// Ymin/Xmin が減少し始める位置を求めます
// isX が true なら Xmin の位置を、そうでなければ Ymin の位置を返します
ll TriSearchMin2(bool isX) {
    ll lb = 1, ub = 200000000;
    while(ub - lb > 1) {
        ll mid = (lb + ub) / 2;
        double val_mid = GetMin(static_cast<double>(mid), isX);
        double val_prev = GetMin(static_cast<double>(mid - 1), isX);
        double val_next = GetMin(static_cast<double>(mid + 1), isX);
        if(val_prev < val_mid && val_mid < val_next)        { ub = mid; }
        else if(val_prev == val_mid && val_mid < val_next)  { ub = mid; }
        else if(val_prev == val_mid && val_mid == val_next) { ub = mid; }
        else if(val_prev > val_mid && val_mid == val_next)  { lb = mid; rb = mid + 1; break; }
        else if(val_prev > val_mid && val_mid > val_next)   { lb = mid; }
        else if(val_prev > val_mid && val_mid < val_next)   { lb = mid; rb = mid + 1; break; }
    }
    // この時点で lb + 1 = ub
    // lb から 0.5 刻みでチェックして厳密な位置を探る
    double mid = static_cast<double>(lb) - 0.5;
    double val_prev = GetMin(mid);
    REP(i, 4) {
        mid += 0.5;
        double val = GetMin(mid);
        if(val_prev <= val) { return mid - 0.5; }
        val_prev = val;
    }

    return mid;
}

double solve() {
    // 以下のタイミングを求める
    //   - Ymax が変わらなくなる位置
    //   - Ymax が再度変わり始める位置
    //   - Ymin が変わらなくなる位置
    //   - Ymin が再度変わり始める位置

    set<double> cand;
    cand.insert(TriSearchMax1(false));
    cand.insert(TriSearchMax2(false));
    cand.insert(TriSearchMin1(false));
    cand.insert(TriSearchMin2(false));

    // X についても同様に求める
    cand.insert(TriSearchMax1(true));
    cand.insert(TriSearchMax2(true));
    cand.insert(TriSearchMin1(true));
    cand.insert(TriSearchMin2(true));

    double ret = GetArea(0);
    for(auto& tmp : cand) {
        ret = min(ret, GetArea(tmp));
    }

    return ret;
}

signed main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    X.resize(N);
    Y.resize(N);
    D.resize(N);
    REP(i, N) {
        cin >> X[i] >> Y[i] >> D[i];
    }

    double ans = solve();
    printf("%.10f\n", ans);

    return 0;
}


Compiler output:
a.cc: In function 'll TriSearchMax1(bool)':
a.cc:98:73: error: 'rb' was not declared in this scope; did you mean 'ub'?
   98 |         else if(val_prev > val_mid && val_mid == val_next)  { lb = mid; rb = mid + 1; break; }
      |                                                                         ^~
      |                                                                         ub
a.cc:100:73: error: 'rb' was not declared in this scope; did you mean 'ub'?
  100 |         else if(val_prev > val_mid && val_mid < val_next)   { lb = mid; rb = mid + 1; break; }
      |                                                                         ^~
      |                                                                         ub
a.cc:105:29: error: too few arguments to function 'double GetMax(double, bool)'
  105 |     double val_prev = GetMax(mid);
      |                       ~~~~~~^~~~~
a.cc:30:8: note: declared here
   30 | double GetMax(double m, bool isX) {
      |        ^~~~~~
a.cc:108:28: error: too few arguments to function 'double GetMax(double, bool)'
  108 |         double val = GetMax(mid);
      |                      ~~~~~~^~~~~
a.cc:30:8: note: declared here
   30 | double GetMax(double m, bool isX) {
      |        ^~~~~~
a.cc: In function 'll TriSearchMax2(bool)':
a.cc:126:73: error: 'rb' was not declared in this scope; did you mean 'ub'?
  126 |         else if(val_prev == val_mid && val_mid < val_next)  { lb = mid; rb = mid + 1; break; }
      |                                                                         ^~
      |                                                                         ub
a.cc:130:73: error: 'rb' was not declared in this scope; did you mean 'ub'?
  130 |         else if(val_prev > val_mid && val_mid < val_next)   { lb = mid; rb = mid + 1; break; }
      |                                                                         ^~
      |                                                                         ub
a.cc:135:29: error: too few arguments to function 'double GetMax(double, bool)'
  135 |     double val_prev = GetMax(mid);
      |                       ~~~~~~^~~~~
a.cc:30:8: note: declared here
   30 | double GetMax(double m, bool isX) {
      |        ^~~~~~
a.cc:138:28: error: too few arguments to function 'double GetMax(double, bool)'
  138 |         double val = GetMax(mid);
      |                      ~~~~~~^~~~~
a.cc:30:8: note: declared here
   30 | double GetMax(double m, bool isX) {
      |        ^~~~~~
a.cc: In function 'll TriSearchMin1(bool)':
a.cc:156:73: error: 'rb' was not declared in this scope; did you mean 'ub'?
  156 |         else if(val_prev == val_mid && val_mid < val_next)  { lb = mid; rb = mid + 1; break; }
      |                                                                         ^~
      |                                                                         ub
a.cc:160:73: error: 'rb' was not declared in this scope; did you mean 'ub'?
  160 |         else if(val_prev > val_mid && val_mid < val_next)   { lb = mid; rb = mid + 1; break; }
      |                                                                         ^~
      |                                                                         ub
a.cc:165:29: error: too few arguments to function 'double GetMin(double, bool)'
  165 |     double val_prev = GetMin(mid);
      |                       ~~~~~~^~~~~
a.cc:48:8: note: declared here
   48 | double GetMin(double m, bool isX) {
      |        ^~~~~~
a.cc:168:28: error: too few arguments to function 'double GetMin(double, bool)'
  168 |         double val = GetMin(mid);
      |                      ~~~~~~^~~~~
a.cc:48:8: note: declared here
   48 | double GetMin(double m, bool isX) {
      |        ^~~~~~
a.cc: In function 'll TriSearchMin2(bool)':
a.cc:188:73: error: 'rb' was not declared in this scope; did you mean 'ub'?
  188 |         else if(val_prev > val_mid && val_mid == val_next)  { lb = mid; rb = mid + 1; break; }
      |                                                                         ^~
      |                                                                         ub
a.cc:190:73: error: 'rb' was not declared in this scope; did you mean 'ub'?
  190 |         else if(val_prev > val_mid && val_mid < val_next)   { lb = mid; rb = mid + 1; break; }
      |                                                                         ^~
      |                                                                         ub
a.cc:195:29: error: too few arguments to function 'double GetMin(double, bool)'
  195 |     double val_prev = GetMin(mid);
      |                       ~~~~~~^~~~~
a.cc:48:8: note: declared here
   48 | double GetMin(double m, bool isX) {
      |        ^~~~~~
a.cc:198:28: error: too few arguments to function 'double GetMin(double, bool)'
  198 |         double val = GetMin(mid);
      |                      ~~~~~~^~~~~
a.cc:48:8: note: declared here
   48 | double GetMin(double m, bool isX) {
      |        ^~~~~~