Submission #8422639

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  int init_x_max, init_x_min, init_y_max, init_y_min;
  init_x_max = init_y_max = INT_MIN;
  init_x_min = init_y_min = INT_MAX;
  int h_y_min, h_y_max, v_x_min, v_x_max;
  h_y_min = v_x_min = INT_MAX;
  h_y_max = v_x_max = INT_MIN;
  int up_y_min, up_y_max, down_y_max, down_y_min, l_x_min, l_x_max, r_x_min, r_x_max;
  up_y_min = down_y_min = l_x_min = r_x_min = INT_MAX;
  up_y_max = down_y_max = l_x_max = r_x_max = INT_MIN;
  double ans;
  for (int i = 0; i < N; i++) {
    int x, y;
    char d;
    cin >> x >> y >>d;
    init_x_max = max(x, init_x_max);
    init_x_min = min(x, init_x_min);
    init_y_max = max(y, init_y_max);
    init_y_min = min(y, init_y_min);
    if (d == 'L') {
      l_x_max = max(x, l_x_max);
      l_x_min = min(x, l_x_min);
    } else if (d == 'R') {
      r_x_max = max(x, r_x_max);
      r_x_min = min(x, r_x_min);
    } else if (d == 'U') {
      up_y_min = min(up_y_min, y);
      up_y_max = max(up_y_max, y);
    } else if (d == 'D') {
      down_y_min = min(down_y_min, y);
      down_y_max = max(down_y_max, y);
    }
    if (d == 'L' || d == 'R') {
      h_y_max = max(h_y_max, y);
      h_y_min = min(h_y_min, y);
    } else {
      v_x_max = max(v_x_max, x);
      v_x_min = min(v_x_min, x);
    }
  }
  ans = (long long)(init_x_max - init_x_min) * (init_y_max - init_y_min);
  vector<double> candidate_time;
  // y_max
  if (up_y_max < h_y_max) {
    candidate_time.push_back(h_y_max - up_y_max);
  }
  if (down_y_max > max(h_y_max, up_y_max)) {
      candidate_time.push_back((down_y_max - up_y_max) / 2.);
      candidate_time.push_back(down_y_max - h_y_max);
  }
  // y_min
  if (down_y_min > h_y_min) {
    candidate_time.push_back(down_y_min - h_y_min);
  }
  if (up_y_min < min(down_y_min, h_y_min)) {
    candidate_time.push_back((down_y_min - up_y_min) / 2.);
    candidate_time.push_back(h_y_min - up_y_min);
  }
  // x_max
  if (r_x_max < v_x_max) {
    candidate_time.push_back(v_x_max - r_x_max);
  }
  if (l_x_max > max(v_x_max, r_x_max)) {
    candidate_time.push_back(l_x_max - v_x_max);
    candidate_time.push_back((l_x_max - r_x_max) / 2.);
  }
  // x_min
  if (l_x_min > v_x_min) {
    candidate_time.push_back(l_x_min - v_x_min);
  }
  if (r_x_min < min(l_x_min, v_x_min)) {
    candidate_time.push_back(v_x_min - r_x_min);
    candidate_time.push_back((l_x_min - r_x_min) / 2.);
  }
  auto calc =[&](double t) {
    double min_x = min({double(v_x_min), l_x_min - t, r_x_min + t});
    double min_y = min({double(h_y_min), up_y_min + t, down_y_min - t});
    double max_x = max({double(v_x_max), l_x_max - t, r_x_max + t});
    double max_y = max({double(h_y_max), up_y_max + t, down_y_max - t});
    ans = min(ans, (max_x - min_x) * (max_y - min_y));
  };
  for (auto t : candidate_time) {
    calc(t);
  }
  cout << fixed << setprecision(10) << ans << '\n';

  
}

Submission Info

Judge Result