← 返回题目列表

AtCoder · abc130_f

F. 最小边界框

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 N 点位于二维平面中。的初始坐标为 i第一点是 (x_i, y_i)。现在,每个点开始以每秒 1 的速度移动,方向与 x- 或 y- 轴。你被赋予了一个角色 d_i 代表具体方向 i第点移动,如下:

  • If d_i = R, i第一点向正方向移动 x 方向;
  • If d_i = L, i第一点向负方向移动 x 方向;
  • If d_i = U, i第一点向正方向移动 y 方向;
  • If d_i = D, i第一点向负方向移动 y 方向。

您可以在所有点开始移动后(包括它们开始移动的那一刻)在您选择的某个时刻停止它们。 然后,让 x_{max} 和 x_{min} 是其中的最大值和最小值 x- 坐标 分别为 N 点。同样,让 分别为 y_{max} 和 y_{min} 是其中的最大值和最小值 y- 坐标 分别为 N 点。

找到以下的最小可能值 (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 is 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}.


示例输入 1

2
0 3 D
3 0 L

示例输出 1

0

三秒后,两点将在原点相遇。所讨论的值将是 0 在那一刻。


示例输入 2

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

示例输出 2

97.5

答案可能不是整数。


示例输入 3

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

示例输出 3

273