AT_abc130_f [ABC130F] Minimum Bounding Box

[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} $ 以下のとき正解とみなされる。

### 制約 - $ 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 出力が整数にならない場合もあります。