F - 最小包围盒

分数：600分

问题描述

在二维平面上有$N$个点。第$i$个点的初始坐标为$(x_i, y_i)$。现在，每个点以每秒1个单位的速度，沿平行于$x$轴或$y$轴的方向移动。给定一个字符$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})$的最小可能值，并输出。

约束

• $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。

输入

标准输入格式如下：

$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

三秒后，两个点将会在原点相遇。题目所求的值在那一刻为$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