[ABC130F] Minimum Bounding Box

### 题目描述 平面上有 $N$ 个点，第 $i$ 个点的坐标是 $(x_i, y_i)$。现在，每个点开始沿着 $x$ 轴或 $y$ 轴方向以 $1$ 格每秒的速度移动。字符 $d_i$ 表示第 $i$ 个点的方向： * 如果 $d_i=$`R`，第 $i$ 个点沿 $x$ 轴正方向移动； * 如果 $d_i=$`L`，第 $i$ 个点沿 $x$ 轴负方向移动； * 如果 $d_i=$`U`，第 $i$ 个点沿 $y$ 轴正方向移动； * 如果 $d_i=$`D`，第 $i$ 个点沿 $y$ 轴负方向移动； 点开始移动后，你可以选择任意一个时刻（包括刚刚开始的那个时刻）停止所有点。停止后，分别记 $x_{max},x_{min}$ 为 $N$ 个点中 $x$ 坐标的最大值、最小值；同样，记 $y_{max},y_{min}$ 为 $N$ 个点中 $y$ 坐标的最大值、最小值。 你需要找出 $(x_{max}-x_{min})\times(y_{max}-y_{min})$ 的最小值并输出这个值。 ### 输入格式 输入来自以下格式的标准输入： --- $ N $ $ x_1 $ $ y_1 $ $ d_1 $ $ x_2 $ $ y_2 $ $ d_2 $ $\vdots$ $ x_N $ $ y_N $ $ d_N $ --- #### 输出格式 输出 $(x_{max}-x_{min})\times(y_{max}-y_{min})$ 可能的最小值。 当与答案的相对误差在 $10^{-9}$ 以内时，你的输出会被认为是正确的。 ### 数据范围 * $1 \le N \le 10^5$。 * $-10^8 \le x_i, y_i \le 10^8$。 * $x_i,y_i$ 都是整数。 * $d_i$ 是 `R`、`L`、`U`、`D` 的其中之一。 ### 样例说明 #### 样例 1/样例 4 第 $3$ 秒，两点在原点相遇，此时的答案是 $0$。 #### 样例 2/样例 5 答案也许不是整数。

[problemUrl]: https://atcoder.jp/contests/abc130/tasks/abc130_f 二次元平面に $ N $ 個の点があります。$ i $ 番目の点の初期座標は $ (x_i,\ y_i) $ です。それぞれの点はこれから秒速 $ 1 $ で同時に移動を始めます。点の移動方向は全て $ x $ 軸または $ y $ 軸に平行です。具体的には $ i $ 番目の点の移動方向は文字 $ d_i $ によって与えられ、 - $ d_i\ = $ `R` のとき $ x $ 軸正方向 - $ d_i\ = $ `L` のとき $ x $ 軸負方向 - $ d_i\ = $ `U` のとき $ y $ 軸正方向 - $ d_i\ = $ `D` のとき $ y $ 軸負方向 です。 あなたは点が移動を開始して以降、任意のタイミングで全ての点の動きを止めることができます (移動開始 $ 0 $ 秒後に止めることも可能です)。 動きを止めたあとの $ N $ 点の $ x $ 座標のうち最大のものを $ x_{max} $、最小のものを $ x_{min} $、$ y $ 座標のうち最大のものを $ y_{max} $、最小のものを $ y_{min} $ とします。 $ (x_{max}\ -\ x_{min})\ \times\ (y_{max}\ -\ y_{min}) $ としてありうる値の最小値を求めて出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ x_1 $ $ y_1 $ $ d_1 $ $ x_2 $ $ y_2 $ $ d_2 $ $ . $ $ . $ $ . $ $ x_N $ $ y_N $ $ d_N $

$ (x_{max}\ -\ x_{min})\ \times\ (y_{max}\ -\ y_{min}) $ としてありうる値の最小値を出力せよ。 ジャッジプログラムの出力との絶対誤差または相対誤差が $ 10^{-9} $ 以下のとき正解とみなされる。

2
0 3 D
3 0 L

0

5
-7 -10 U
7 -6 U
-8 7 D
-3 3 D
0 -6 R

97.5

20
6 -10 R
-4 -9 U
9 6 D
-3 -2 R
0 7 D
4 5 D
10 -10 U
-1 -8 U
10 -6 D
8 -5 U
6 4 D
0 3 D
7 9 R
9 -4 R
3 10 D
1 9 U
1 -6 U
9 -8 R
6 7 D
7 -3 D

273

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ -10^8\ \leq\ x_i,\ y_i\ \leq\ 10^8 $ - $ x_i $, $ \ y_i $ はともに整数である。 - $ d_i $ は `R`, `L`, `U`, `D` のいずれかである。 ### Sample Explanation 1 $ 3 $ 秒後に $ 2 $ つの点は原点で重なり、このとき題意の値は $ 0 $ になります。 ### Sample Explanation 2 出力が整数にならない場合もあります。