题目描述

二次元平面に $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}$ 以下のとき正解とみなされる。

题目大意

题目描述

平面上有 $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

答案也许不是整数。

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

出力が整数にならない場合もあります。