There are N points in a two-dimensional plane. The initial coordinates of the i-th point are (x_i, y_i). Now, each point starts moving at a speed of 1 per second, in a direction parallel to the x- or y- axis. You are given a character d_i that represents the specific direction in which the i-th point moves, as follows:
 - If d_i = R, the i-th point moves in the positive x direction;
 - If d_i = L, the i-th point moves in the negative x direction;
 - If d_i = U, the i-th point moves in the positive y direction;
 - If d_i = D, the i-th point moves in the negative y direction.
You can stop all the points at some moment of your choice after they start moving (including the moment they start moving).
Then, let x_{max} and x_{min} be the maximum and minimum among the x-coordinates of the N points, respectively. Similarly, let y_{max} and y_{min} be the maximum and minimum among the y-coordinates of the N points, respectively.
Find the minimum possible value of (x_{max} - x_{min}) \times (y_{max} - y_{min}) and print it.

-----Constraints-----
 - 1 \leq N \leq 10^5
 - -10^8 \leq x_i,\ y_i \leq 10^8
 - x_i and y_i are integers.
 - d_i is R, L, U, or D.

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 y_1 d_1
x_2 y_2 d_2
.
.
.
x_N y_N d_N

-----Output-----
Print the minimum possible value of (x_{max} - x_{min}) \times (y_{max} - y_{min}).
The output will be considered correct when its absolute or relative error from the judge's output is at most 10^{-9}.

-----Sample Input-----
2
0 3 D
3 0 L

-----Sample Output-----
0

After three seconds, the two points will meet at the origin. The value in question will be 0 at that moment.

Difficulty: interview

Starter code:

Solutions:

from itertools import combinations

INF = float("inf")
data = {d: [-INF, INF, -INF, INF] for d in 'RLUD'}

_, *XYD = open(0).read().split()
X = map(int, XYD[::3])
Y = map(int, XYD[1::3])
D = map(data.get, XYD[2::3])

for x, y, d in zip(X, Y, D):
    d[0] = max(d[0], x)
    d[1] = min(d[1], x)
    d[2] = max(d[2], y)
    d[3] = min(d[3], y)


X = [
    (data["L"][0], -1), (data["L"][1], -1),
    (data["R"][0], 1), (data["R"][1], 1),
    (data["U"][0], 0), (data["U"][1], 0),
    (data["D"][0], 0), (data["D"][1], 0),
]
Y = [
    (data["L"][2], 0), (data["L"][3], 0),
    (data["R"][2], 0), (data["R"][3], 0),
    (data["U"][2], 1), (data["U"][3], 1),
    (data["D"][2], -1), (data["D"][3], -1),
]

X = [(x, dx) for x, dx in X if abs(x) < INF]
Y = [(y, dy) for y, dy in Y if abs(y) < INF]

T = set(
    [0] +
    [max(0, (x - y) / (dy - dx)) for (x, dx), (y, dy) in combinations(X, 2) if dx != dy] +
    [max(0, (x - y) / (dy - dx)) for (x, dx), (y, dy) in combinations(Y, 2) if dx != dy]
)


def area(t):
    XX = [t * dx + x for x, dx in X]
    YY = [t * dy + y for y, dy in Y]

    dx = max(XX) - min(XX)
    dy = max(YY) - min(YY)

    return dx * dy


print(min(map(area, T)))

I = float('inf')
N = int(input())
XYD = [input().split() for _ in range(N)]
xL = set()
xR = set()
xS = set()
yD = set()
yU = set()
yS = set()
for xyd in XYD:
    x, y, d = xyd
    x = int(x)
    y = int(y)
    if d == 'L':
        xL.add(x)
        yS.add(y)
    elif d == 'R':
        xR.add(x)
        yS.add(y)
    elif d == 'U':
        yU.add(y)
        xS.add(x)
    else:
        yD.add(y)
        xS.add(x)
#xmin
xRmin = min(xR | {I})
xLmin = min(xL | {I})
xSmin = min(xS | {I})
#xmax
xRmax = max(xR | {-I})
xLmax = max(xL | {-I})
xSmax = max(xS | {-I})

x2m = xLmax - xRmin
x1m = max(xSmax - xRmin, xLmax - xSmin)
x0 = max(xRmax - xRmin, xLmax - xLmin, xSmax - xSmin)
x1 = max(xSmax - xLmin, xRmax - xSmin)
x2 = xRmax - xLmin
#ymin
yUmin = min(yU | {I})
yDmin = min(yD | {I})
ySmin = min(yS | {I})
#ymax
yUmax = max(yU | {-I})
yDmax = max(yD | {-I})
ySmax = max(yS | {-I})

y2m = yDmax - yUmin
y1m = max(ySmax - yUmin, yDmax - ySmin)
y0 = max(yUmax - yUmin, yDmax - yDmin, ySmax - ySmin)
y1 = max(ySmax - yDmin, yUmax - ySmin)
y2 = yUmax - yDmin


def dd(t):
    if 0 <= t < I:
        return max(x2m - 2 * t, x1m - t, x0, x1 + t, x2 + 2 * t) * max(
            y2m - 2 * t, y1m - t, y0, y1 + t, y2 + 2 * t)
    else:
        return I


t = [0, x2m / 2, x1m, y2m / 2, y1m]
t += [x2m - x1m, x1m - x0, x0 - x1, x1 - x2]
t += [(x2m - x0) / 2, (x1m - x1) / 2, (x0 - x2) / 2]
t += [(x2m - x1) / 3, (x1m - x2) / 3]
t += [(x2m - x2) / 4]
t += [y2m - y1m, y1m - y0, y0 - y1, y1 - y2]
t += [(y2m - y0) / 2, (y1m - y1) / 2, (y0 - y2) / 2]
t += [(y2m - y1) / 3, (y1m - y2) / 3]
t += [(y2m - y2) / 4]
t += [(x2m + y2m) / 4, (x2 + y2) / 4]
t += [(x2m + 2 * y1m) / 4, (y1m + 2 * x2m) / 4, (x2 + 2 * y1) / 4,
      (y1 + 2 * x2) / 4]
t += [(x1m + y1m) / 2, (x1 + y1) / 2]

print((min([dd(time) for time in t])))


n = int(input())
R = []
L = []
U = []
D = []
lm = [float("INF")]*3
rm = [-float("INF")]*3
dm = [float("INF")]*3
um = [-float("INF")]*3
for i in range(n):
    x,y,d = input().split()
    x = int(x)
    y = int(y)
    if d == "U":
        rm[1] = max(rm[1],x)
        lm[1] = min(lm[1],x)
        dm[0] = min(dm[0],y)
        um[2] = max(um[2],y)
        U.append((x,y,d))
    elif d == "D":
        rm[1] = max(rm[1],x)
        lm[1] = min(lm[1],x)
        um[0] = max(um[0],y)
        dm[2] = min(dm[2],y)
        D.append((x,y,d))
    elif d == "L":
        um[1] = max(um[1],y)
        dm[1] = min(dm[1],y)
        rm[0] = max(rm[0],x)
        lm[2] = min(lm[2],x)
        L.append((x,y,d))
    else:
        um[1] = max(um[1],y)
        dm[1] = min(dm[1],y)
        lm[0] = min(lm[0],x)
        rm[2] = max(rm[2],x)
        R.append((x,y,d))
time = set()
def rc(t):
    if rm[2] == max(rm):
        return rm[2]+t
    if rm[1] == max(rm):
        if rm[2] == -float("INF"):
            return rm[1]
        else:
            time.add(rm[1]-rm[2])
            return max(rm[1],rm[2]+t)
    if rm[2] == -float("INF") and rm[1] == -float("INF"):
        return rm[0]-t
    if rm[2] == -float("INF"):
        time.add(rm[0]-rm[1])
        return max(rm[1],rm[0]-t)
    if rm[1] == -float("INF"):
        time.add((rm[0]-rm[2])/2)
        return max(rm[0]-t,rm[2]+t)
    if (rm[0]-rm[2])/2+rm[2] >= rm[1]:
        time.add((rm[0]-rm[2])/2)
        return max(rm[0]-t,rm[2]+t)
    time.add(rm[0]-rm[1])
    time.add(rm[1]-rm[2])
    return max(rm[0]-t,rm[2]+t,rm[1])
def lc(t):
    if lm[2] == min(lm):
        return lm[2]-t
    if lm[1] == min(lm):
        if lm[2] == float("INF"):
            return lm[1]
        else:
            time.add(-lm[1]+lm[2])
            return min(lm[1],lm[2]-t)
    if lm[2] == float("INF") and lm[1] == float("INF"):
        return lm[0]+t
    if lm[2] == float("INF"):
        time.add(-lm[0]+lm[1])
        return min(lm[1],lm[0]+t)
    if lm[1] == float("INF"):
        time.add((-lm[0]+lm[2])/2)
        return min(lm[0]+t,lm[2]-t)
    if lm[2]-(-lm[0]+lm[2])/2 <= lm[1]:
        time.add((-lm[0]+lm[2])/2)
        return min(lm[0]+t,lm[2]-t)
    time.add(-lm[0]+lm[1])
    time.add(-lm[1]+lm[2])
    return min(lm[0]+t,lm[2]-t,lm[1])
def uc(t):
    if um[2] == max(um):
        return um[2]+t
    if um[1] == max(um):
        if um[2] == -float("INF"):
            return um[1]
        else:
            time.add(um[1]-um[2])
            return max(um[1],um[2]+t)
    if um[2] == -float("INF") and um[1] == -float("INF"):
        return um[0]-t
    if um[2] == -float("INF"):
        time.add(um[0]-um[1])
        return max(um[1],um[0]-t)
    if um[1] == -float("INF"):
        time.add((um[0]-um[2])/2)
        return max(um[0]-t,um[2]+t)
    if (um[0]-um[2])/2+um[2] >= um[1]:
        time.add((um[0]-um[2])/2)
        return max(um[0]-t,um[2]+t)
    time.add(um[0]-um[1])
    time.add(um[1]-um[2])
    return max(um[0]-t,um[2]+t,um[1])
def dc(t):
    if dm[2] == min(dm):
        return dm[2]-t
    if dm[1] == min(dm):
        if dm[2] == float("INF"):
            return dm[1]
        else:
            time.add(-dm[1]+dm[2])
            return min(dm[1],dm[2]-t)
    if dm[2] == float("INF") and dm[1] == float("INF"):
        return dm[0]+t
    if dm[2] == float("INF"):
        time.add(-dm[0]+dm[1])
        return min(dm[1],dm[0]+t)
    if dm[1] == float("INF"):
        time.add((-dm[0]+dm[2])/2)
        return min(dm[0]+t,dm[2]-t)
    if dm[2]-(-dm[0]+dm[2])/2 <= dm[1]:
        time.add((-dm[0]+dm[2])/2)
        return min(dm[0]+t,dm[2]-t)
    time.add(-dm[0]+dm[1])
    time.add(-dm[1]+dm[2])
    return min(dm[0]+t,dm[2]-t,dm[1])
ans = (rc(0)-lc(0))*(uc(0)-dc(0))
for t in time:
    count = (rc(t)-lc(t))*(uc(t)-dc(t))
    ans = min(ans,count)
print(ans)

import bisect
import heapq
import sys


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class V:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)

    def get(self):
        return self.v


def read_values():
    return list(map(int, input().split()))


def read_list():
    return list(read_values())


def calc_v(D, f, i):
    p, n, c = V(f), V(f), V(f)
    for d, P in list(D.items()):
        for pp in P:
            if d == ("R" if i == 0 else "U"):
                p.ud(pp[i])
            elif d == ("L" if i == 0 else "D"):
                n.ud(pp[i])
            else:
                c.ud(pp[i])

    p = p.get()
    n = n.get()
    c = c.get()
    return p, n, c, f


def calc_e(p, n, c, f):
    if p is None:
        if c is None or n is None:
            return []
        else:
            return [n - c]

    if n is None:
        if c is None:
            return []
        else:
            return [c - p]

    t = (n - p) / 2
    if c is None:
        return [t]

    return [t, c - p, n - c]


def calc(t, L):
    res = V(L[3])
    if L[0] is not None:
        res.ud(L[0] + t)

    if L[1] is not None:
        res.ud(L[1] - t)

    if L[2] is not None:
        res.ud(L[2])

    return res.get()


def main():
    N = int(input())
    D = {
        "R": [],
        "L": [],
        "U": [],
        "D": [],
    }

    for _ in range(N):
        x, y, d = input().split()
        x = int(x)
        y = int(y)
        D[d].append((x, y))

    VV = []
    VV.append(calc_v(D, max, 0))
    VV.append(calc_v(D, min, 0))
    VV.append(calc_v(D, max, 1))
    VV.append(calc_v(D, min, 1))

    E = {0}
    for e in [calc_e(*v) for v in VV]:
        for t in e:
            E.add(t)

    res = V(min)
    for t in E:
        if t < 0:
            continue
        res.ud((calc(t, VV[0]) - calc(t, VV[1])) * (calc(t, VV[2]) - calc(t, VV[3])))
    print(res)


def __starting_point():
    main()

__starting_point()

import os
import sys

import numpy as np
from scipy.optimize import fmin

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
X, Y, D = list(zip(*[sys.stdin.readline().rstrip().split() for _ in range(N)]))
X = np.array(X, dtype=int)
Y = np.array(Y, dtype=int)
D = np.array(D)

Rmin = min(list(X[D == 'R']) + [INF])
Rmax = max(list(X[D == 'R']) + [-INF])
Lmin = min(list(X[D == 'L']) + [INF])
Lmax = max(list(X[D == 'L']) + [-INF])
Umin = min(list(Y[D == 'U']) + [INF])
Umax = max(list(Y[D == 'U']) + [-INF])
Dmin = min(list(Y[D == 'D']) + [INF])
Dmax = max(list(Y[D == 'D']) + [-INF])

Xmin = min(list(X[(D == 'U') | (D == 'D')]) + [INF])
Xmax = max(list(X[(D == 'U') | (D == 'D')]) + [-INF])
Ymin = min(list(Y[(D == 'R') | (D == 'L')]) + [INF])
Ymax = max(list(Y[(D == 'R') | (D == 'L')]) + [-INF])


def cost(t):
    if t < 0:
        return -t + 10 ** 18
    xl = min(Xmin, Lmin - t, Rmin + t)
    xr = max(Xmax, Lmax - t, Rmax + t)
    yb = min(Ymin, Dmin - t, Umin + t)
    yt = max(Ymax, Dmax - t, Umax + t)
    return (xr - xl) * (yt - yb)


x, = fmin(cost, x0=100000, ftol=10 ** -10, disp=False)
print(('{:.10f}'.format(cost(x))))


dirs = {'R': (1, 0), 'L': (-1, 0), 'U': (0, 1), 'D': (0, -1)}

N = int(input())
P = {d: [] for d in dirs}
for i in range(N):
    x, y, d = input().split()
    x, y = list(map(int, (x, y)))
    P[d].append((x, y))

def fst(x): return x[0]
def snd(x): return x[1]
inf = float('inf')

# 方向別のX・Yの最大最小
S = {d: {'xmin': min(list(map(fst, P[d])), default= inf),
         'xmax': max(list(map(fst, P[d])), default=-inf),
         'ymin': min(list(map(snd, P[d])), default= inf),
         'ymax': max(list(map(snd, P[d])), default=-inf) }
     for d in dirs}

# 変化がある時刻は0と以下のt1, t2, t3
# S[L][xmax] - t1 == max(S[U][xmax], S[D][xmax]), t < t1 -> S[UD] < S[L]
# S[R][xmax] + t2 == max(S[U][xmax], S[D][xmax]), t < t2 -> S[R]  < S[UD]
# S[L][xmax] - t3 == S[R][xmax] + t3,             t < t3 -> S[R]  < S[L]

dirs = {d: {'x': dirs[d][0], 'y': dirs[d][1]} for d in dirs}
vars = ('xmax', 'xmin', 'ymax', 'ymin')
maxmin = {'max': max, 'min': min}
maxmin = {v: maxmin[v[-3:]] for v in vars}

# 変化がある時刻の集合
T = set()
T.add(0)
for v in vars:
    u, d, c1, c2 = ('R', 'L', 'U', 'D') if v.startswith('x') else \
                   ('U', 'D', 'R', 'L')
    C  = maxmin[v](S[c1][v], S[c2][v])
    t1 =  S[d][v] - C  # inf - inf == nan
    t2 = -S[u][v] + C
    t3 = (S[d][v] - S[u][v]) / 2
    T.update([t1, t2, t3])

# 各時刻のxmax, xmin, ymax, yminを計算
q = inf
for t in (t for t in T if 0 <= t < inf):
    Q = {v: maxmin[v](S[d][v] + t * dirs[d][v[0]] for d in dirs)
         for v in vars}
    q = min(q, (Q['xmax'] - Q['xmin']) * (Q['ymax'] - Q['ymin']))

print(q)


inf = float('inf')
N = int(input())
MRp = -inf
MR = -inf
MRm = -inf
mRp = inf
mR = inf
mRm = inf
MUp = -inf
MU = -inf
MUm = -inf
mUp = inf
mU = inf
mUm = inf

for i in range(N):
	x, y, d = input().split()
	x, y = int(x), int(y)
	if d == 'R':
		MRp = max(MRp, x)
		mRp = min(mRp, x)
		MU = max(MU, y)
		mU = min(mU, y)
	elif d == 'L':
		MRm = max(MRm, x)
		mRm = min(mRm, x)
		MU = max(MU, y)
		mU = min(mU, y)
	elif d == 'U':
		MUp = max(MUp, y)
		mUp = min(mUp, y)
		MR = max(MR, x)
		mR = min(mR, x)
	else:
		MUm = max(MUm, y)
		mUm = min(mUm, y)
		MR = max(MR, x)
		mR = min(mR, x)

t = [0]
if MR > max(MRp, MRm):
	t.append(MR - MRp)
elif MRm + MRp >= 2 * MR and MRm > MRp:
	t.append((MRm - MRp) / 2)
elif MRm > MRp:
	t.append(MRm - MR)
	t.append(MR - MRp)	
if mR < min(mRp, mRm):
	t.append(mRm - mR)
elif mRm + mRp <= 2 * mR and mRm > mRp:
	t.append((mRm - mRp) / 2)
elif mRm > mRp:
	t.append(mRm - mR)
	t.append(mR - mRp)
if MU > max(MUp, MUm):
	t.append(MU - MUp)
elif MUm + MUp >= 2 * MU and MUm > MUp:
	t.append((MUm - MUp) / 2)
elif MUm > MUp:
	t.append(MUm - MU)
	t.append(MU - MUp)
if mU < min(mUp, mUm):
	t.append(mUm - mU)
elif mUm + mUp <= 2 * mU and mUm > mUp:
	t.append((mUm - mUp) / 2)
elif mUm > mUp:
	t.append(mUm - mU)
	t.append(mU - mUp)

ans = inf
for i in t:
	dx = max(MRp + i, MR, MRm - i) - min(mRp + i, mR, mRm - i)
	dy = max(MUp + i, MU, MUm - i) - min(mUp + i, mU, mUm - i)
	ans = min(ans, dx * dy)
print(ans)

n = int(input())
xyd = [list(input().split()) for i in range(n)]
xmax,ymax = [-10**9,-10**9,-10**9],[-10**9,-10**9,-10**9]
xmin,ymin = [10**9,10**9,10**9],[10**9,10**9,10**9]
#xmax: max(x1-t,x2,x3+t)
#xmin: min(x1+t,x2,x3-t)
#ymax: max(y1-t,y2,y3+t)
#ymin: min(y1+t,y2,y3-t)
def chp(ls,a,flg1,i):
  if flg1:
    ls[i] = max(ls[i],a)
  else:
    ls[i] = min(ls[i],a)
def area(t):
  x = max(xmax[0]-t,xmax[1],xmax[2]+t)-min(xmin[0]+t,xmin[1],xmin[2]-t)
  y = max(ymax[0]-t,ymax[1],ymax[2]+t)-min(ymin[0]+t,ymin[1],ymin[2]-t)
  return x*y
for x,y,d in xyd:
  x,y = int(x),int(y)
  if d in ("L","R"):
    chp(ymax,y,1,1)
    chp(ymin,y,0,1)
    if d == "R":
      chp(xmin,x,0,0)
      chp(xmax,x,1,2)
    if d == "L":
      chp(xmin,x,0,2)
      chp(xmax,x,1,0)
  elif d in ("U","D"):
    chp(xmax,x,1,1)
    chp(xmin,x,0,1)
    if d == "U":
      chp(ymax,y,1,2)
      chp(ymin,y,0,0)
    if d == "D":
      chp(ymin,y,0,2)
      chp(ymax,y,1,0)

event = [0]
for ls in xmax,ymax:
  event.append(ls[0]-ls[1])
  event.append((ls[0]-ls[2])/2)
  event.append(ls[1]-ls[2])
for ls in xmin,ymin:
  event.append(ls[1]-ls[0])
  event.append((ls[2]-ls[0])/2)
  event.append(ls[2]-ls[1])
ans = 10**18

for i in event:
  if i>=0:
    for j in range(-10,10):
      if i+j*0.5 >= 0:
        ans = min(ans,area(i+j*0.5))
print(ans)

#!/usr/bin/env python3
import sys

inf = float('inf')

def solve(N: int, x: "List[int]", y: "List[int]", d: "List[str]"):
    D_xmin = [inf for dd in [-1, 0, 1]]
    D_xmax = [-inf for dd in [-1, 0, 1]]
    D_ymin = [inf for dd in [-1, 0, 1]]
    D_ymax = [-inf for dd in [-1, 0, 1]]
    trans_x = {'U': 1, 'D': 1, 'L': 0, 'R': 2}
    trans_y = {'U': 2, 'D': 0, 'L': 1, 'R': 1}
    
    for xx, yy, dd in zip(x, y, d):
        D_xmin[trans_x[dd]] = min(D_xmin[trans_x[dd]], xx)
        D_xmax[trans_x[dd]] = max(D_xmax[trans_x[dd]], xx)
        D_ymin[trans_y[dd]] = min(D_ymin[trans_y[dd]], yy)
        D_ymax[trans_y[dd]] = max(D_ymax[trans_y[dd]], yy)
    
    ts = [0]
    for D in [D_xmin, D_xmax, D_ymin, D_ymax]:
        ts.append(D[0] - D[1])
        ts.append(D[1] - D[2])
        ts.append((D[0] - D[2]) / 2)

    res = inf
    for t in ts:
        if t < 0:
            continue
        xmin = min(D_xmin[0] - t, D_xmin[1], D_xmin[2] + t)
        xmax = max(D_xmax[0] - t, D_xmax[1], D_xmax[2] + t)
        ymin = min(D_ymin[0] - t, D_ymin[1], D_ymin[2] + t)
        ymax = max(D_ymax[0] - t, D_ymax[1], D_ymax[2] + t)
        res = min(res, (xmax - xmin) * (ymax - ymin))

    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    d = [str()] * (N)  # type: "List[str]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        d[i] = next(tokens)
    solve(N, x, y, d)

def __starting_point():
    main()

__starting_point()

import numpy as np
from scipy.optimize import fmin

INF = 10**18

mapping = {
    "R": (1, 0),
    "L": (-1, 0),
    "U": (0, 1),
    "D": (0, -1)
}

def f(x, vx, t):
    if t < 0:
        return INF
    nx = x + vx * t
    return nx.max() - nx.min()

def solve(n, x, y, d):
    x = np.asarray(x, dtype=np.float)
    y = np.asarray(y, dtype=np.float)
    vx = np.zeros(n, dtype=np.float)
    vy = np.zeros(n, dtype=np.float)
    for i in range(n):
        vx[i], vy[i] = mapping[d[i]]
    h = lambda t: f(y, vy, t) * f(x, vx, t)
    t = fmin(h, x0=10**8, ftol=1e-9, disp=False)[0]
    return h(t)

n = int(input())
x, y, d = [-1]*n, [-1]*n, [-1]*n
for i in range(n):
    x[i], y[i], d[i] = input().split()
    x[i] = int(x[i])
    y[i] = int(y[i])
print(solve(n, x, y, d))

import sys

def main():
    input = sys.stdin.readline
    inf = 10**8 + 1
    N = int(input())
    const_x_max, right_max, left_max = -inf, -inf, -inf
    const_x_min, right_min, left_min = inf, inf, inf
    const_y_max, up_max, down_max = -inf, -inf, -inf
    const_y_min, up_min, down_min = inf, inf, inf
    for _ in range(N):
        x, y, d = list(map(str, input().strip().split()))
        x, y = int(x), int(y)

        if d == 'R':
            right_max = max(right_max, x)
            right_min = min(right_min, x)
            const_y_max = max(const_y_max, y)
            const_y_min = min(const_y_min, y)
        elif d == 'L':
            left_max = max(left_max, x)
            left_min = min(left_min, x)
            const_y_max = max(const_y_max, y)
            const_y_min = min(const_y_min, y)
        elif d == 'U':
            const_x_max = max(const_x_max, x)
            const_x_min = min(const_x_min, x)
            up_max = max(up_max, y)
            up_min = min(up_min, y)
        else:
            const_x_max = max(const_x_max, x)
            const_x_min = min(const_x_min, x)
            down_max = max(down_max, y)
            down_min = min(down_min, y)

    inflections = set([0])
    # The time when the slope of max_x changes.
    # 1. from decrease to constant.
    inflections.add(max(0, left_max - const_x_max))
    # 2. from decrease to increase.
    inflections.add(max(0, (left_max - right_max)/2))
    # 3. from constant to increase.
    inflections.add(max(0, const_x_max - right_max))

    # The time when the slope of min_x changes.
    # 4. from increase to constatnt.
    inflections.add(max(0, const_x_min - right_min))
    # 5. from increase to decrease.
    inflections.add(max(0, (left_min - right_min)/2))
    # 6. from constant to decrease.
    inflections.add(max(0, left_min - const_x_min))

    # The time when the slope of max_y changes.
    # 7. from decrease to constant.
    inflections.add(max(0, down_max - const_y_max))
    # 8. from decrease to increase.
    inflections.add(max(0, (down_max - up_max)/2))
    # 9. from constant to increase.
    inflections.add(max(0, const_y_max - up_max))

    # The time when the slope of min_y changes.
    # 10. from increase to constatnt.
    inflections.add(max(0, const_y_min - up_min))
    # 11. from increase to decrease.
    inflections.add(max(0, (down_min - up_min)/2))
    # 12. from constant to decrease.
    inflections.add(max(0, down_min - const_y_min))


    def get_val(t):
        x0 = max(const_x_max, right_max + t, left_max - t)
        x1 = min(const_x_min, right_min + t, left_min - t)
        y0 = max(const_y_max, up_max + t, down_max - t)
        y1 = min(const_y_min, up_min + t, down_min - t)

        return (x0 - x1) * (y0 - y1)

    ans = 10**18
    for t in inflections:
        ans = min(ans, get_val(t))

    return ans


def __starting_point():
    print((main()))

__starting_point()

inf = float('inf')
from scipy.optimize import fmin
from collections import defaultdict
dir = {'R', 'L', 'U', 'D'}
N = int(input())
dic = defaultdict(list)
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    dic[d].append((x, y))
x_max = defaultdict(lambda : -inf)
x_min = defaultdict(lambda : inf)
y_max = defaultdict(lambda : -inf)
y_min = defaultdict(lambda : inf)
for d in dir:
    if dic[d]:
        dic[d].sort()
        x_max[d] = dic[d][-1][0]
        x_min[d] = dic[d][0][0]
        dic[d].sort(key = lambda x:x[1])
        y_max[d] = dic[d][-1][1]
        y_min[d] = dic[d][0][1]
def dx(t):
    return max(x_max['U'], x_max['D'], x_max['R']+t, x_max['L']-t)-min(x_min['U'], x_min['D'], x_min['R']+t, x_min['L']-t)
def dy(t):
    return max(y_max['U']+t, y_max['D']-t, y_max['R'], y_max['L'])-min(y_min['U']+t, y_min['D']-t, y_min['R'], y_min['L'])
def f(t):
    if t<0:
        return inf
    return dx(t)*dy(t)

xopt = fmin(f, x0 = 10**8, ftol = 10**-9, disp = False)
print((f(xopt[0])))













inf = float("inf")
N = int(input())
if N==1:
    print((0))
    return
lr = inf
ll = inf
rr = -inf
rl = -inf
ud = -inf
uu = -inf
dd = inf
du = inf
l_stop = inf
r_stop = -inf
u_stop = -inf
d_stop = inf
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    if d=="R":
        lr = min(lr, x)
        rr = max(rr, x)
    elif d=="L":
        rl = max(rl, x)
        ll = min(ll, x)
    elif d=="U":
        du = min(du, y)
        uu = max(uu, y)
    else:
        ud = max(ud, y)
        dd = min(dd, y)
    if d=="R" or d=="L":
        u_stop = max(u_stop, y)
        d_stop = min(d_stop, y)
    else:
        l_stop = min(l_stop, x)
        r_stop = max(r_stop, x)


def f(t):
    r = max(r_stop, rr+t, rl-t)
    l = min(l_stop, ll-t, lr+t)
    u = max(u_stop, uu+t, ud-t)
    d = min(d_stop, dd-t, du+t)
    return (r-l) * (u-d)
#print(f(1))

high = 10**8
high = float(high)
low = 0.0
while high - low > 0.000001:
    #print(high, low)
    mid_left = high/3+low*2/3
    mid_right = high*2/3+low/3
    if f(mid_left) >= f(mid_right):
        low = mid_left
    else:
        high = mid_right
print((f(round(high, 3))))


import sys
input = sys.stdin.readline

INF = 10**18

N = int(input())
D = []
U = []
L = []
R = []
UD = []
LR = []
for _ in range(N):
    str_x, str_y, d = map(str, input().rstrip().split())
    x = int(str_x)
    y = int(str_y)
    if d == "U":
        U.append(y)
        UD.append(x)
    elif d == "D":
        D.append(y)
        UD.append(x)
    elif d == "L":
        L.append(x)
        LR.append(y)
    else:
        R.append(x)
        LR.append(y)

UD.sort()
LR.sort()
U.sort()
D.sort()
L.sort()
R.sort()

T = [0]
if L and R:
    T.append((L[0]-R[0])/2)
    T.append((L[-1]-R[-1])/2)
if L and UD:
    T.append(L[0]-UD[0])
    T.append(L[-1]-UD[-1])
if R and UD:
    T.append(UD[0]-R[0])
    T.append(UD[-1]-R[-1])
if U and D:
    T.append((D[0]-U[0])/2)
    T.append((D[-1]-U[-1])/2)
if U and LR:
    T.append(-U[0]+LR[0])
    T.append(-U[-1]+LR[-1])
if D and LR:
    T.append(-LR[0]+D[0])
    T.append(-LR[-1]+D[-1])

ans = INF
for t in T:
    if t < 0: continue
    l = INF
    r = -INF
    d = INF
    u = -INF
    if L:
        l = min(l, L[0]-t)
        r = max(r, L[-1]-t)
    if R:
        l = min(l, R[0]+t)
        r = max(r, R[-1]+t)
    if U:
        d = min(d, U[0]+t)
        u = max(u, U[-1]+t)
    if D:
        d = min(d, D[0]-t)
        u = max(u, D[-1]-t)
    if LR:
        d = min(d, LR[0])
        u = max(u, LR[-1])
    if UD:
        l = min(l, UD[0])
        r = max(r, UD[-1])
    ans = min(ans, (r-l)*(u-d))

print(ans)

import sys


def check(t):
    maxx = max(ud_maxx, r_maxx + t, l_maxx - t)
    minx = min(ud_minx, r_minx + t, l_minx - t)
    maxy = max(lr_maxy, u_maxy + t, d_maxy - t)
    miny = min(lr_miny, u_miny + t, d_miny - t)
    return (maxx - minx) * (maxy - miny)


n = int(input())
lr_maxy, lr_miny, ud_maxx, ud_minx = -1e9, 1e9, -1e9, 1e9
l_maxx, l_minx, r_maxx, r_minx = -1e9, 1e9, -1e9, 1e9
u_maxy, u_miny, d_maxy, d_miny = -1e9, 1e9, -1e9, 1e9
for line in sys.stdin:
    x, y, d = line.rstrip().split()
    x, y = int(x), int(y)
    if d == 'L':
        lr_maxy = max(lr_maxy, y)
        lr_miny = min(lr_miny, y)
        l_maxx = max(l_maxx, x)
        l_minx = min(l_minx, x)
    elif d == 'R':
        lr_maxy = max(lr_maxy, y)
        lr_miny = min(lr_miny, y)
        r_maxx = max(r_maxx, x)
        r_minx = min(r_minx, x)
    elif d == 'U':
        ud_maxx = max(ud_maxx, x)
        ud_minx = min(ud_minx, x)
        u_maxy = max(u_maxy, y)
        u_miny = min(u_miny, y)
    else:
        ud_maxx = max(ud_maxx, x)
        ud_minx = min(ud_minx, x)
        d_maxy = max(d_maxy, y)
        d_miny = min(d_miny, y)

inflections = {0}
inflections.add(max(0, l_maxx - ud_maxx))
inflections.add(max(0, (l_maxx - r_maxx) / 2))
inflections.add(max(0, ud_maxx - r_maxx))
inflections.add(max(0, l_minx - ud_minx))
inflections.add(max(0, (l_minx - r_minx) / 2))
inflections.add(max(0, ud_minx - r_minx))

inflections.add(max(0, d_maxy - lr_maxy))
inflections.add(max(0, (d_maxy - u_maxy) / 2))
inflections.add(max(0, lr_maxy - u_maxy))
inflections.add(max(0, d_miny - lr_miny))
inflections.add(max(0, (d_miny - u_miny) / 2))
inflections.add(max(0, lr_miny - u_miny))

print((min(list(map(check, inflections)))))


N = int(input())
lm = [float("INF")]*3
rm = [-float("INF")]*3
um = [-float("INF")]*3
dm = [float("INF")]*3

for i in range(N):
    x,y,d = input().split()
    x = int(x)
    y = int(y)
    if d == "L":
        um[1] = max(um[1],y)
        dm[1] = min(dm[1],y)
        lm[2] = min(lm[2],x)
        rm[0] = max(rm[0],x)
    if d == "R":
        um[1] = max(um[1],y)
        dm[1] = min(dm[1],y)
        lm[0] = min(lm[0],x)
        rm[2] = max(rm[2],x)
    if d == "U":
        um[2] = max(um[2],y)
        dm[0] = min(dm[0],y)
        lm[1] = min(lm[1],x)
        rm[1] = max(rm[1],x)
    if d == "D":
        um[0] = max(um[0],y)
        dm[2] = min(dm[2],y)
        lm[1] = min(lm[1],x)
        rm[1] = max(rm[1],x)

time = [0]

def calc(t):
    x = max(rm[1],rm[0]-t,rm[2]+t) -min(lm[1],lm[0]+t,lm[2]-t)
    y = max(um[1],um[0]-t,um[2]+t) -min(dm[1],dm[0]+t,dm[2]-t)
    return x*y

for i in range(3):
    for j in range(i):
        t = (lm[i]-lm[j])/(i-j)
        if t > 0:
            time.append(t)
        t = (dm[i]-dm[j])/(i-j)
        if t > 0:
            time.append(t)
        t = (rm[j]-rm[i])/(i-j)
        if t > 0:
            time.append(t)
        t = (um[j]-um[i])/(i-j)
        if t > 0:
            time.append(t)

ans = float("INF")
for t in time:
    ans = min(ans,calc(t))
print(ans)

from collections import defaultdict
N=int(input())

xlist,ylist=[],[]
for i in range(N):
  xs,ys,d=input().split()
  x=int(xs)
  y=int(ys)
  if d=="L":
    xlist.append((x,-1))
    ylist.append((y,0))
  elif d=="R":
    xlist.append((x,1))
    ylist.append((y,0))
  elif d=="U":
    xlist.append((x,0))
    ylist.append((y,1))
  else:
    xlist.append((x,0))
    ylist.append((y,-1))
#print(xlist,ylist)

xdic=defaultdict(set)
for x,d in xlist:
  xdic[d].add(x)
#print(xdic)
xlist2=[]
for d in [-1,0,1]:
  if len(xdic[d]):
    min_d=min(xdic[d])
    max_d=max(xdic[d])
    xlist2.append((min_d,d))
    xlist2.append((max_d,d))
  
ydic=defaultdict(set)
for y,d in ylist:
  ydic[d].add(y)
#print(ydic)
ylist2=[]
for d in [-1,0,1]:
  if len(ydic[d]):
    min_d=min(ydic[d])    
    max_d=max(ydic[d])
    ylist2.append((min_d,d))
    ylist2.append((max_d,d))
#print(xlist2,ylist2)

def cand_time(plist):
  ret=set()
  for i in range(len(plist)):
    p1,d1=plist[i]
    for j in range(i+1,len(plist)):
      p2,d2=plist[j]
      if d1==d2:
        continue
        
      if d1==-1:
        if d2==0:
          t=p1-p2
        else:
          t=(p1-p2)/2
      elif d1==0:
        if d2==-1:
          t=p2-p1
        else:
          t=p1-p2
      else:
        if d2==-1:
          t=(p2-p1)/2
        else:
          t=p2-p1
       
      if t>0:
        ret.add(t)
  return ret

cand_time_x=cand_time(xlist2)
cand_time_y=cand_time(ylist2)
#print(cand_time_x,cand_time_y)
cand_t=[0]+list(cand_time_x)+list(cand_time_y)
#print(cand_t)

def get_pos(pd,t):
  p,d=pd
  return p+d*t

answer=float("inf")
for t in cand_t:
  pos_min_x=float("inf")
  pos_max_x=-float("inf")
  for x2 in xlist2:
    pos_min_x=min(pos_min_x,get_pos(x2,t))
    pos_max_x=max(pos_max_x,get_pos(x2,t))
    
  pos_min_y=float("inf")
  pos_max_y=-float("inf")
  for y2 in ylist2:
    pos_min_y=min(pos_min_y,get_pos(y2,t))
    pos_max_y=max(pos_max_y,get_pos(y2,t))

  #print(t,pos_min_x,pos_max_x,pos_min_y,pos_max_y)
  t_ans=abs(pos_max_x-pos_min_x)*abs(pos_max_y-pos_min_y)
  if answer>=t_ans:
    answer=t_ans
    #print(answer,t,abs(pos_max_x-pos_min_x),abs(pos_max_y-pos_min_y))
  
print(answer)

import itertools
N = int(input())
LX, LY = [], []
RX, RY = [], []
DX, DY = [], []
UX, UY = [], []

for _ in range(N):
  x,y,d = input().split()
  x,y = int(x), int(y)
  if d == 'L':
    LX.append(x)
    LY.append(y)
  elif d == 'R':
    RX.append(x)
    RY.append(y)
  elif d == 'U':
    UX.append(x)
    UY.append(y)
  else:
    DX.append(x)
    DY.append(y)

INF = 10**18
fixed_x = [min(UX + DX + [INF]), max(UX + DX + [-INF])]
fixed_y = [min(LY + RY + [INF]), max(LY + RY + [-INF])]

R_x = [min(RX + [INF]), max(RX + [-INF])]
L_x = [min(LX + [INF]), max(LX + [-INF])]
U_y = [min(UY + [INF]), max(UY + [-INF])]
D_y = [min(DY + [INF]), max(DY + [-INF])]


# 2点が衝突する時刻を除けば1次関数
T = [0]

for x1,x2 in itertools.product(L_x, R_x):
  if x1 in [-INF, INF] or x2 in [-INF, INF]:
    continue
  T.append((x1 - x2) / 2)
for x1,x2 in itertools.product(L_x, fixed_x):
  if x1 in [-INF, INF] or x2 in [-INF, INF]:
    continue
  T.append(x1 - x2)
for x1,x2 in itertools.product(R_x, fixed_x):
  if x1 in [-INF, INF] or x2 in [-INF, INF]:
    continue
  T.append(x2 - x1)
  
for x1,x2 in itertools.product(D_y, U_y):
  if x1 in [-INF, INF] or x2 in [-INF, INF]:
    continue
  T.append((x1 - x2) / 2)
for x1,x2 in itertools.product(D_y, fixed_y):
  if x1 in [-INF, INF] or x2 in [-INF, INF]:
    continue
  T.append(x1 - x2)
for x1,x2 in itertools.product(U_y, fixed_y):
  if x1 in [-INF, INF] or x2 in [-INF, INF]:
    continue
  T.append(x2 - x1)
  
T = sorted(set(t for t in T if t >= 0))
T.append(10 ** 9)

def calc_x(t):
  # t秒後の横幅
  right = fixed_x[1]
  left = fixed_x[0]
  for x in [R_x[1]+t, L_x[1]-t]:
    if right < x:
      right = x
  for x in [R_x[0]+t, L_x[0]-t]:
    if left > x:
      left = x
  return right - left

def calc_y(t):
  # t秒後の横幅
  right = fixed_y[1]
  left = fixed_y[0]
  for y in [U_y[1]+t, D_y[1]-t]:
    if right < y:
      right = y
  for y in [U_y[0]+t, D_y[0]-t]:
    if left > y:
      left = y
  return right - left

def F(x1,x2,y1,y2):
  # x は x1からx2に向かう1次関数
  # y は y1からy2に向かう1次関数
  # t in [0,1] で関数を作る
  # x = (x2-x1)t + x1
  # y = (y2-y1)t + y1
  p,q,r,s = x2-x1, x1, y2-y1, y1
  a,b,c = p*r, p*s + q*r, q*s
  # f(t) = at^2 + bt + c
  if a <= 0:
    # 直線 or 上に凸
    return min(x1*y1, x2*y2)
  t0 = -b/(2*a)
  if t0 < 0 or t0 > 1:
    return min(x1*y1, x2*y2)
  return min(a*t0*t0 + b*t0 + c, a+b+c, c)
  
L = len(T)
X = [calc_x(t) for t in T]
Y = [calc_y(t) for t in T]

answer = 10 ** 18

for i in range(L-1):
  x1, x2 = X[i], X[i+1]
  y1, y2 = Y[i], Y[i+1]
  s = F(x1,x2,y1,y2)
  if answer > s:
    answer = s

print(answer)

n = int(input())
xyd = [input().split() for _ in range(n)]


x_max_RL_ = [-2e8] * 3
x_min_RL_ = [2e8] * 3
y_max_UD_ = [-2e8] * 3
y_min_UD_ = [2e8] * 3

for x, y, d in xyd:
    x = int(x)
    y = int(y)

    if d == "R":
        ho, ve = 2, 1
    elif d == "L":
        ho, ve = 0, 1
    elif d == "U":
        ho, ve = 1, 2
    else:  # d == "D"
        ho, ve = 1, 0
    x_max_RL_[ho] = max(x_max_RL_[ho], x)
    x_min_RL_[ho] = min(x_min_RL_[ho], x)
    y_max_UD_[ve] = max(y_max_UD_[ve], y)
    y_min_UD_[ve] = min(y_min_UD_[ve], y)

kouho_time = set([0])

for _max_min in [x_max_RL_, x_min_RL_, y_max_UD_, y_min_UD_]:
    for i in range(0, 3):
        if abs(_max_min[i]) <= 1e8:
            for j in range(i + 1, 3):
                if abs(_max_min[j]) <= 1e8:
                    cross = (_max_min[i] - _max_min[j]) / (j - i)
                    if cross > 0:
                        kouho_time.add(cross)


ans = 4e16
for t in kouho_time:
    x_max = max(
        x_max_RL_[i] + t * (i - 1) for i in range(3) if abs(x_max_RL_[i]) <= 1e8
    )
    x_min = min(
        x_min_RL_[i] + t * (i - 1) for i in range(3) if abs(x_min_RL_[i]) <= 1e8
    )
    y_max = max(
        y_max_UD_[i] + t * (i - 1) for i in range(3) if abs(y_max_UD_[i]) <= 1e8
    )
    y_min = min(
        y_min_UD_[i] + t * (i - 1) for i in range(3) if abs(y_min_UD_[i]) <= 1e8
    )

    ans = min(ans, (x_max - x_min) * (y_max - y_min))

print(ans)


def analyze(points, left_static, right_static):
    """
    (x0, +1 or -1) in points
    """

    rightest_neg = -10**9
    leftest_neg = 10**9
    rightest_pos = -10**9
    leftest_pos = 10**9
    for x, d in points:
        if d == 1:
            rightest_pos = max(rightest_pos, x)
            leftest_pos = min(leftest_pos, x)
        else:
            rightest_neg = max(rightest_neg, x)
            leftest_neg = min(leftest_neg, x)


    max_t1 = rightest_neg - right_static
    max_t2 = right_static - rightest_pos
    if max_t1 > max_t2:
        max_t1 = max_t2 = (rightest_neg-rightest_pos)/2
    max_t1 = max(0, max_t1)
    max_t2 = max(0, max_t2)
    max_x0 = max(rightest_pos, rightest_neg, right_static)
    max_x1 = max(rightest_pos + max_t1, rightest_neg - max_t1, right_static)
    def get_xmax(t):
        if t > max_t2:
            return max_x1 + t-max_t2
        elif t > max_t1:
            return max_x1
        else:
            return max_x0 - t

    min_t1 = left_static - leftest_pos
    min_t2 = leftest_neg - left_static
    if min_t1 > min_t2:
        min_t1 = min_t2 = (leftest_neg - leftest_pos)/2
    min_t1 = max(0, min_t1)
    min_t2 = max(0, min_t2)
    min_x0 = min(leftest_pos, leftest_neg, left_static)
    min_x1 = min(leftest_pos + min_t1, leftest_neg - min_t1, left_static)

    def get_xmin(t):
        if t > min_t2:
            return min_x1 - t + min_t2
        elif t > min_t1:
            return min_x1
        else:
            return min_x0 + t

    T = sorted((max_t1, max_t2, min_t1, min_t2))
    D = [get_xmax(t)-get_xmin(t) for t in T]
    return T,D



N = int(input())

conv = {'R':0,'U':1,'L':2,'D':3}
points = [(lambda i: (int(i[0]), int(i[1]), conv[i[2]]))(input().split()) for _ in range(N)]


xt, xd = analyze([(x, 1 if d == 0 else -1) for x,y,d in points if d%2==0],
                    min((x for x,y,d in points if d%2==1), default=10**9),
                    max((x for x,y,d in points if d%2==1), default=-10**9))

yt, yd = analyze([(y, 1 if d == 1 else -1) for x,y,d in points if d%2==1],
                    min((y for x,y,d in points if d%2==0), default=10**9),
                    max((y for x,y,d in points if d%2==0), default=-10**9))

def get_w(t):
    a,b,c,d = xt

    if t < a:
        return -2, xd[0] + 2*a
    elif t < b:
        return -1, xd[0] + a
    elif t < c:
        return 0, xd[1]
    elif t < d:
        return 1, xd[2] - c
    else:
        return 2, xd[3] - 2*d

def get_h(t):
    a,b,c,d = yt

    if t < a:
        return -2, yd[0] + 2*a
    elif t < b:
        return -1, yd[0] + a
    elif t < c:
        return 0, yd[1]
    elif t < d:
        return 1, yd[2] - c
    else:
        return 2, yd[3] - 2*d

T = sorted(xt+yt)

def it():
    ne = iter(T)
    next(ne)
    for a,b in zip(T,ne):
        t = (a+b)/2

        wa, wb = get_w(t)
        ha, hb = get_h(t)
        if wa*ha > 0 and a < -(wb*ha+wa*hb)/(2*wa*ha) < b:
            t = -(wb*ha+wa*hb)/(2*wa*ha)
            yield ((wa*t+wb)*(ha*t+hb), t)
        else:
            yield ((wa*a+wb)*(ha*a+hb), a)
            yield ((wa*b+wb)*(ha*b+hb), b)

print(min(it())[0])

###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    nonlocal mod
    return (x + y) % mod


def modmlt(x, y):
    nonlocal mod
    return (x * y) % mod


def mod_inv(x):
    # available only when mod is prime
    nonlocal mod
    return pow(x, mod - 2, mod)


def gcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in list(distance_list.items()):
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


def find_edge(plus, nt, minus):
    ret = []
    if plus is not None and nt is not None and plus <= nt:
        ret.append(nt - plus)
    if minus is not None and nt is not None and minus >= nt:
        ret.append(minus - nt)
    if plus is not None and minus is not None and plus <= minus:
        ret.append((minus - plus) / 2)
    return ret


def calc_coord(t, plus, nt, minus, ismax=False):
    check = []
    if plus is not None:
        check.append(plus + t)
    if nt is not None:
        check.append(nt)
    if minus is not None:
        check.append(minus - t)
    if ismax:
        return max(check)
    return min(check)


def main():
    n = intin()
    xydlist = []
    for _ in range(n):
        line = input()
        line = line.split()
        x = int(line[0])
        y = int(line[1])
        d = line[2]
        xydlist.append((x, y, d))

    xplusmax = None
    xminusmax = None
    xntmax = None

    xplusmin = None
    xminusmin = None
    xntmin = None

    yplusmax = None
    yminusmax = None
    yntmax = None

    yplusmin = None
    yminusmin = None
    yntmin = None

    for x, y, d in xydlist:
        if d == 'R':
            xplusmax = x if xplusmax is None else max(xplusmax, x)
            yntmax = y if yntmax is None else max(yntmax, y)
            xplusmin = x if xplusmin is None else min(xplusmin, x)
            yntmin = y if yntmin is None else min(yntmin, y)
        if d == 'L':
            xminusmax = x if xminusmax is None else max(xminusmax, x)
            yntmax = y if yntmax is None else max(yntmax, y)
            xminusmin = x if xminusmin is None else min(xminusmin, x)
            yntmin = y if yntmin is None else min(yntmin, y)
        if d == 'U':
            xntmax = x if xntmax is None else max(xntmax, x)
            yplusmax = y if yplusmax is None else max(yplusmax, y)
            xntmin = x if xntmin is None else min(xntmin, x)
            yplusmin = y if yplusmin is None else min(yplusmin, y)
        if d == 'D':
            xntmax = x if xntmax is None else max(xntmax, x)
            yminusmax = y if yminusmax is None else max(yminusmax, y)
            xntmin = x if xntmin is None else min(xntmin, x)
            yminusmin = y if yminusmin is None else min(yminusmin, y)

    tlist = [0]
    tlist.extend(find_edge(xplusmax, xntmax, xminusmax))
    tlist.extend(find_edge(xplusmin, xntmin, xminusmin))
    tlist.extend(find_edge(yplusmax, yntmax, yminusmax))
    tlist.extend(find_edge(yplusmin, yntmin, yminusmin))

    tlist = list(set(tlist))
    ans = float('inf')

    for t in tlist:
        x_max = calc_coord(t, xplusmax, xntmax, xminusmax, ismax=True)
        x_min = calc_coord(t, xplusmin, xntmin, xminusmin, ismax=False)
        y_max = calc_coord(t, yplusmax, yntmax, yminusmax, ismax=True)
        y_min = calc_coord(t, yplusmin, yntmin, yminusmin, ismax=False)
        ans = min(ans, (x_max - x_min) * (y_max - y_min))

    if ans == float('inf'):
        print((0))
    else:
        print(ans)


def __starting_point():
    main()

__starting_point()

dirs = {'R': (1, 0), 'L': (-1, 0), 'U': (0, 1), 'D': (0, -1)}

N = int(input())
P = {d: [] for d in dirs}
for i in range(N):
    x, y, d = input().split()
    x, y = list(map(int, (x, y)))
    P[d].append((x, y))

def fst(x): return x[0]
def snd(x): return x[1]
inf = float('inf')

# 方向別のX・Yの最大最小
S = {d: {'xmin': min(list(map(fst, P[d])), default= inf),
         'xmax': max(list(map(fst, P[d])), default=-inf),
         'ymin': min(list(map(snd, P[d])), default= inf),
         'ymax': max(list(map(snd, P[d])), default=-inf) }
     for d in dirs}

vars = ('xmax', 'xmin', 'ymax', 'ymin')
maxmin = {'max': max, 'min': min}
dirs = {d: {'x': dirs[d][0], 'y': dirs[d][1]} for d in dirs}

# S[L][xmax] - t1 == max(S[U][xmax], S[D][xmax])  t < t1 -> S[UD] < S[L]
# S[R][xmax] + t2 == max(S[U][xmax], S[D][xmax])  t < t2 -> S[R]  < S[UD]
# S[L][xmax] - t3 == S[R][xmax] + t3              t < t3 -> S[R]  < S[L]

# 変化がある時刻の集合
T = set()
T.add(0)
for v in vars:
    u, d, c1, c2 = ('R', 'L', 'U', 'D') if v.startswith('x') else \
                   ('U', 'D', 'R', 'L')
    C  = maxmin[v[-3:]](S[c1][v], S[c2][v])
    t1 =  S[d][v] - C
    t2 = -S[u][v] + C
    t3 = (S[d][v] - S[u][v]) / 2
    T.update([t1, t2, t3])

q = inf
for t in (t for t in T if 0 <= t and t != inf):
    Q = {v: maxmin[v[-3:]](S[d][v] + t * dirs[d][v[0]] for d in dirs)
         for v in vars}
    q = min(q, (Q['xmax'] - Q['xmin']) * (Q['ymax'] - Q['ymin']))

print(q)


import sys
def input():
	return sys.stdin.readline()[:-1]

INF = 10**30
n = int(input())
p = [input().split() for _ in range(n)]

"""
[0]: max or min / for
[1]: max or min / against
[2]: max or min / fixed
"""

r = [-INF, -INF, -INF]
l = [INF, INF, INF]
u = [-INF, -INF, -INF]
d = [INF, INF, INF]

for x, y, t in p:
	x, y = int(x), int(y)
	if t == "R":
		r[0] = max(r[0], x)
		l[1] = min(l[1], x)
		u[2] = max(u[2], y)
		d[2] = min(d[2], y)
	elif t == "L":
		r[1] = max(r[1], x)
		l[0] = min(l[0], x)
		u[2] = max(u[2], y)
		d[2] = min(d[2], y)
	elif t == "U":
		r[2] = max(r[2], x)
		l[2] = min(l[2], x)
		u[0] = max(u[0], y)
		d[1] = min(d[1], y)
	else:
		r[2] = max(r[2], x)
		l[2] = min(l[2], x)
		u[1] = max(u[1], y)
		d[0] = min(d[0], y)

#print(r)
#print(l)
#print(u)
#print(d)

timings = set([0])

if r[0] <= r[1] <= r[2]:
	timings.add(abs(r[2]-r[0]))
elif r[0] <= r[2] <= r[1]:
	timings.add(abs(r[1]-r[0])/2)
	timings.add(abs(r[2]-r[0]))
	timings.add(abs(r[1]-r[2]))
elif r[1] <= r[0] <= r[2]:
	timings.add(abs(r[2]-r[0]))
elif r[2] <= r[0] <= r[1]:
	timings.add(abs(r[1]-r[0])/2)

if l[0] >= l[1] >= l[2]:
	timings.add(abs(l[2]-l[0]))
elif l[0] >= l[2] >= l[1]:
	timings.add(abs(l[1]-l[0])/2)
	timings.add(abs(l[2]-l[0]))
	timings.add(abs(l[1]-l[2]))
elif l[1] >= l[0] >= l[2]:
	timings.add(abs(l[2]-l[0]))
elif l[2] >= l[0] >= l[1]:
	timings.add(abs(l[1]-l[0])/2)

if u[0] <= u[1] <= u[2]:
	timings.add(abs(u[2]-u[0]))
elif u[0] <= u[2] <= u[1]:
	timings.add(abs(u[1]-u[0])/2)
	timings.add(abs(u[2]-u[0]))
	timings.add(abs(u[1]-u[2]))
elif u[1] <= u[0] <= u[2]:
	timings.add(abs(u[2]-u[0]))
elif u[2] <= u[0] <= u[1]:
	timings.add(abs(u[1]-u[0])/2)

if d[0] >= d[1] >= d[2]:
	timings.add(abs(d[2]-d[0]))
elif d[0] >= d[2] >= d[1]:
	timings.add(abs(d[1]-d[0])/2)
	timings.add(abs(d[2]-d[0]))
	timings.add(abs(d[1]-d[2]))
elif d[1] >= d[0] >= d[2]:
	timings.add(abs(d[2]-d[0]))
elif d[2] >= d[0] >= d[1]:
	timings.add(abs(d[1]-d[0])/2)

#print(timings)
ans = 10**30
for t in timings:
	if t > 10**10:
		continue
	R, L, U, D = -INF, INF, -INF, INF
	for x, y, di in p:
		if di == "R":
			x, y = int(x)+t, int(y)
		elif di == "L":
			x, y = int(x)-t, int(y)
		elif di == "U":
			x, y = int(x), int(y)+t
		else:
			x, y = int(x), int(y)-t

		R = max(R, x)
		L = min(L, x)
		U = max(U, y)
		D = min(D, y)

	ans = min(ans, (R-L)*(U-D))

print(ans)

import queue

"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
def s(time,maxX,minX,maxY,minY,maxU,minU,maxD,minD,maxL,minL,maxR,minR):
	mxx = []
	mnx = []
	mxy = []
	mny = []
	if maxX != None:
		mxx.append(maxX)
		mnx.append(minX)
	if maxY != None:
		mxy.append(maxY)
		mny.append(minY)
	if maxR != None:
		mxx.append(maxR+time)
		mnx.append(minR+time)
	if maxL != None:
		mxx.append(maxL-time)
		mnx.append(minL-time)
	if maxU != None:
		mxy.append(maxU+time)
		mny.append(minU+time)
	if maxD != None:
		mxy.append(maxD-time)
		mny.append(minD-time)
	mxx = max(mxx)
	mnx = min(mnx)
	mxy = max(mxy)
	mny = min(mny)
	return (mxx-mnx)*(mxy-mny)

N = int(input())

E = [[t if i==2 else int(t) for i,t in enumerate(input().split(" "))]for _ in range(N)]
U = [d[0:2] for d in E if d[2]=="U"]
D = [d[0:2] for d in E if d[2]=="D"]
L = [d[0:2] for d in E if d[2]=="L"]
R = [d[0:2] for d in E if d[2]=="R"]

if len(U+D)>0:
	maxX = max(U+D,key=lambda x:x[0])[0]
	minX = min(U+D,key=lambda x:x[0])[0]
else:
	maxX=None
	minX=None

if len(L+R)>0:
	maxY = max(L+R,key=lambda x:x[1])[1]
	minY = min(L+R,key=lambda x:x[1])[1]
else:
	maxY=None
	minY=None

if len(U)>0:
	maxU = max(U,key=lambda x:x[1])[1]
	minU = min(U,key=lambda x:x[1])[1]
else:
	maxU=None
	minU=None

if len(D)>0:
	maxD = max(D,key=lambda x:x[1])[1]
	minD = min(D,key=lambda x:x[1])[1]
else:
	maxD=None
	minD=None

if len(L)>0:
	maxL = max(L,key=lambda x:x[0])[0]
	minL = min(L,key=lambda x:x[0])[0]
else:
	maxL=None
	minL=None

if len(R)>0:
	maxR = max(R,key=lambda x:x[0])[0]
	minR = min(R,key=lambda x:x[0])[0]
else:
	maxR=None
	minR=None

watch = [0]
min_ans = s(0,maxX,minX,maxY,minY,maxU,minU,maxD,minD,maxL,minL,maxR,minR)

if maxU != None:
	if maxY != None:
		if minY > maxU:
			watch.append(minY-maxU)
		if minY > minU:
			watch.append(minY-minU)
		if maxY > maxU:
			watch.append(maxY-maxU)
		if maxY > minU:
			watch.append(maxY-minU)
	if maxD != None:
		if minD > maxU:
			watch.append((minD-maxU)/2)
		if maxD > maxU:
			watch.append((maxD-maxU)/2)
		if minD > minU:
			watch.append((minD-minU)/2)
		if maxD > minU:
			watch.append((maxD-minU)/2)
if maxD != None:
	if maxY != None:
		if minY < maxD:
			watch.append(maxD-minY)
		if minY < minD:
			watch.append(minD-minY)
		if maxY < maxD:
			watch.append(maxD-maxY)
		if maxY < minD:
			watch.append(minD-maxY)


if maxR != None:
	if maxX != None:
		if minX > maxR:
			watch.append(minX-maxR)
		if minX > minR:
			watch.append(minX-minR)
		if maxX > maxR:
			watch.append(maxX-maxR)
		if maxX > minR:
			watch.append(maxX-minR)
	if maxL != None:
		if minL > maxR:
			watch.append((minL-maxR)/2)
		if maxL > maxR:
			watch.append((maxL-maxR)/2)
		if minL > minR:
			watch.append((minL-minR)/2)
		if maxL > minR:
			watch.append((maxL-minR)/2)
if maxL != None:
	if maxX != None:
		if minX < maxL:
			watch.append(maxL-minX)
		if minX < minL:
			watch.append(minL-minX)
		if maxX < maxL:
			watch.append(maxL-maxX)
		if maxX < minL:
			watch.append(minL-maxX)

for t in watch:
	p = s(t,maxX,minX,maxY,minY,maxU,minU,maxD,minD,maxL,minL,maxR,minR)
	if p < min_ans:
		min_ans = p

print(min_ans)

































from scipy.optimize import fmin
INF = 10**18
n = int(input())
# 0:static, 1:up, 2:down
xpoints = [[] for _ in range(3)]
ypoints = [[] for _ in range(3)]
for i in range(n):
    x, y, d = [item for item in input().split()]
    x = int(x); y = int(y)
    if d == "R":
        ypoints[0].append(y)
        xpoints[1].append(x)
    elif d == "L":
        ypoints[0].append(y)
        xpoints[2].append(x)
    elif d == "U":
        xpoints[0].append(x)
        ypoints[1].append(y)
    elif d == "D":
        xpoints[0].append(x)
        ypoints[2].append(y)
for i in range(3):
    xpoints[i].sort()
    ypoints[i].sort()

def f(t):
    if t < 0:
        return INF 
    max_x = max_y = -INF
    min_x = min_y = INF
    for i, a in enumerate([0, t, -t]):
        if not len(xpoints[i]) == 0:
            max_x = max(max_x, xpoints[i][-1] + a)
            min_x = min(min_x, xpoints[i][0] + a)
        if not len(ypoints[i]) == 0:
            max_y = max(max_y, ypoints[i][-1] + a)
            min_y = min(min_y, ypoints[i][0] + a)
    return (max_x - min_x) * (max_y - min_y)

ans = fmin(f, x0=10**8, ftol= 1e-9, disp=False)
print(f(ans[0]))

N = int(input())

PS = [[], [], [], []]
S = "RLUD".index

for i in range(N):
    x, y, d = input().split(); x = int(x); y = int(y)
    PS[S(d)].append((x, y))

T = [0]
INF = 10**9

dymin = INF; dymax = -INF
P = []
for i in [0, 1]:
    xmin = INF; xmax = -INF
    for x, y in PS[i]:
        dymin = min(dymin, y)
        dymax = max(dymax, y)
        xmin = min(xmin, x)
        xmax = max(xmax, x)
    P.append((xmin, xmax))
for x0 in P[0]:
    for x1 in P[1]:
        T.append(max(x1 - x0, 0) / 2.)

dxmin = INF; dxmax = -INF
Q = []
for i in [2, 3]:
    ymin = INF; ymax = -INF
    for x, y in PS[i]:
        dxmin = min(dxmin, x)
        dxmax = max(dxmax, x)
        ymin = min(ymin, y)
        ymax = max(ymax, y)
    Q.append((ymin, ymax))
for y0 in Q[0]:
    for y1 in Q[1]:
        T.append(max(y1 - y0, 0) / 2.)

for x0 in [dxmin, dxmax]:
    for x in P[0]:
        T.append(max(x0 - x, 0))
    for x in P[1]:
        T.append(max(x - x0, 0))
for y0 in [dymin, dymax]:
    for y in Q[0]:
        T.append(max(y0 - y, 0))
    for y in Q[1]:
        T.append(max(y - y0, 0))

ans = 10**30
for t in T:
    xmin = dxmin; xmax = dxmax
    ymin = dymin; ymax = dymax

    xi, xa = P[0]
    if xi != INF:
        xmin = min(xmin, xi+t)
        xmax = max(xmax, xa+t)
    xi, xa = P[1]
    if xi != INF:
        xmin = min(xmin, xi-t)
        xmax = max(xmax, xa-t)
    yi, ya = Q[0]
    if yi != INF:
        ymin = min(ymin, yi+t)
        ymax = max(ymax, ya+t)
    yi, ya = Q[1]
    if yi != INF:
        ymin = min(ymin, yi-t)
        ymax = max(ymax, ya-t)
    ans = min(ans, (xmax - xmin) * (ymax - ymin))
print("%.10f" % ans)

from scipy.optimize import fmin

N = int(input())

INF = 10 ** 18

X, Y = [[],[],[]], [[],[],[]]
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)

    if d == "R":
        X[0].append(x)
    elif d == "L":
        X[1].append(x)
    else:
        X[2].append(x)

    if d == "U":
        Y[0].append(y)
    elif d == "D":
        Y[1].append(y)
    else:
        Y[2].append(y)

for i in range(3):
    X[i] = [min(X[i] + [INF]), max(X[i] + [-INF])]
    Y[i] = [min(Y[i] + [INF]), max(Y[i] + [-INF])]

def calc_area(t):
    if t < 0:
        return INF

    x_l, x_r = INF, -INF
    x_l, x_r = min(x_l, X[0][0] + i*t), max(x_r, X[0][1] + i*t)
    x_l, x_r = min(x_l, X[1][0] - i*t), max(x_r, X[1][1] - i*t)
    x_l, x_r = min(x_l, X[2][0]      ), max(x_r, X[2][1]      )

    y_l, y_r = INF, -INF
    y_l, y_r = min(y_l, Y[0][0] + i*t), max(y_r, Y[0][1] + i*t)
    y_l, y_r = min(y_l, Y[1][0] - i*t), max(y_r, Y[1][1] - i*t)
    y_l, y_r = min(y_l, Y[2][0]      ), max(y_r, Y[2][1]      )

    return (x_r-x_l) * (y_r-y_l)
    
opt = fmin(calc_area, x0 = 10**8, ftol=10**(-10), disp=False)
print(calc_area(opt[0]))

import itertools
N = int(input())
LX, LY = [], []
RX, RY = [], []
DX, DY = [], []
UX, UY = [], []

for _ in range(N):
  x,y,d = input().split()
  x,y = int(x), int(y)
  if d == 'L':
    LX.append(x)
    LY.append(y)
  elif d == 'R':
    RX.append(x)
    RY.append(y)
  elif d == 'U':
    UX.append(x)
    UY.append(y)
  else:
    DX.append(x)
    DY.append(y)

INF = 10**18
fixed_x = [min(UX + DX + [INF]), max(UX + DX + [-INF])]
fixed_y = [min(LY + RY + [INF]), max(LY + RY + [-INF])]

R_x = [min(RX + [INF]), max(RX + [-INF])]
L_x = [min(LX + [INF]), max(LX + [-INF])]
U_y = [min(UY + [INF]), max(UY + [-INF])]
D_y = [min(DY + [INF]), max(DY + [-INF])]

def calc_x(t):
  # t秒後の横幅
  right = fixed_x[1]
  left = fixed_x[0]
  for x in [R_x[1]+t, L_x[1]-t]:
    if right < x:
      right = x
  for x in [R_x[0]+t, L_x[0]-t]:
    if left > x:
      left = x
  return right - left

def calc_y(t):
  # t秒後の横幅
  right = fixed_y[1]
  left = fixed_y[0]
  for y in [U_y[1]+t, D_y[1]-t]:
    if right < y:
      right = y
  for y in [U_y[0]+t, D_y[0]-t]:
    if left > y:
      left = y
  return right - left

def area(t):
  if t < 0:
    return INF
  return calc_x(t) * calc_y(t)

from scipy.optimize import fmin
xopt = fmin(area, x0 = 10**8, ftol = 10**-9, disp = False)
answer = area(xopt[0])
print(answer)


n = int(input())

x_fix_max = None
x_fix_min = None
x_inc_max = None
x_inc_min = None
x_dec_max = None
x_dec_min = None

y_fix_max = None
y_fix_min = None
y_inc_max = None
y_inc_min = None
y_dec_max = None
y_dec_min = None

for i in range(n):
    x, y, d = [a for a in input().split()]
    if d == "R":
        if x_inc_max is None or x_inc_max < int(x):
            x_inc_max = int(x)
        if x_inc_min is None or x_inc_min > int(x):
            x_inc_min = int(x)
        if y_fix_max is None or y_fix_max < int(y):
            y_fix_max = int(y)
        if y_fix_min is None or y_fix_min > int(y):
            y_fix_min = int(y)
    if d == "L":
        if x_dec_max is None or x_dec_max < int(x):
            x_dec_max = int(x)
        if x_dec_min is None or x_dec_min > int(x):
            x_dec_min = int(x)
        if y_fix_max is None or y_fix_max < int(y):
            y_fix_max = int(y)
        if y_fix_min is None or y_fix_min > int(y):
            y_fix_min = int(y)
    if d == "U":
        if y_inc_max is None or y_inc_max < int(y):
            y_inc_max = int(y)
        if y_inc_min is None or y_inc_min > int(y):
            y_inc_min = int(y)
        if x_fix_max is None or x_fix_max < int(x):
            x_fix_max = int(x)
        if x_fix_min is None or x_fix_min > int(x):
            x_fix_min = int(x)
    if d == "D":
        if y_dec_max is None or y_dec_max < int(y):
            y_dec_max = int(y)
        if y_dec_min is None or y_dec_min > int(y):
            y_dec_min = int(y)
        if x_fix_max is None or x_fix_max < int(x):
            x_fix_max = int(x)
        if x_fix_min is None or x_fix_min > int(x):
            x_fix_min = int(x)

if x_inc_min is None:
    x_inc_min = 10 ** 10
if x_dec_min is None:
    x_dec_min = 10 ** 10
if x_fix_min is None:
    x_fix_min = 10 ** 10
if x_inc_max is None:
    x_inc_max = -10 ** 10
if x_dec_max is None:
    x_dec_max = -10 ** 10
if x_fix_max is None:
    x_fix_max = -10 ** 10
if y_inc_min is None:
    y_inc_min = 10 ** 10
if y_dec_min is None:
    y_dec_min = 10 ** 10
if y_fix_min is None:
    y_fix_min = 10 ** 10
if y_inc_max is None:
    y_inc_max = -10 ** 10
if y_dec_max is None:
    y_dec_max = -10 ** 10
if y_fix_max is None:
    y_fix_max = -10 ** 10

t_list = [0]
t_list += [-x_inc_max + x_fix_max, x_dec_max - x_fix_max, (x_dec_max - x_inc_max) / 2]
t_list += [-y_inc_max + y_fix_max, y_dec_max - y_fix_max, (y_dec_max - y_inc_max) / 2]
t_list += [-x_inc_min + x_fix_min, x_dec_min - x_fix_min, (x_dec_min - x_inc_min) / 2]
t_list += [-y_inc_min + y_fix_min, y_dec_min - y_fix_min, (y_dec_min - y_inc_min) / 2]


min_mult = None
for t in t_list:
    if t < 0:
        continue
    x_max = max(x_inc_max + t, x_fix_max, x_dec_max - t)
    x_min = min(x_inc_min + t, x_fix_min, x_dec_min - t)
    y_max = max(y_inc_max + t, y_fix_max, y_dec_max - t)
    y_min = min(y_inc_min + t, y_fix_min, y_dec_min - t)
    mult = (x_max - x_min) * (y_max - y_min)
    if min_mult is None or min_mult > mult:
        min_mult = mult
print((str(min_mult)))


from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN

def want(n):

    xmax = float("-inf")
    xmin = float("inf")
    ymax = float("-inf")
    ymin = float("inf")

    if L:
        xmax = max(xmax,L_R - n)
        xmin = min(xmin,L_L - n)
        ymax = max(ymax,LR_U)
        ymin = min(ymin,LR_D)

    if R:
        xmax = max(xmax,R_R + n)
        xmin = min(xmin,R_L + n)
        ymax = max(ymax,LR_U)
        ymin = min(ymin,LR_D)

    if D:
        xmax = max(xmax,UD_R)
        xmin = min(xmin,UD_L)
        ymax = max(ymax,D_U - n)
        ymin = min(ymin,D_D - n)

    if U:
        xmax = max(xmax,UD_R)
        xmin = min(xmin,UD_L)
        ymax = max(ymax,U_U + n)
        ymin = min(ymin,U_D + n)

    #print (xmax-xmin,ymax-ymin)
    return abs(xmax - xmin) * abs(ymax - ymin)

def my_round(val, digit=0):
    p = 10 ** digit
    return (val * p * 2 + 1) // 2 / p


N = int(input())

UD_L = float("inf")
UD_R = float("-inf")
L_L = float("inf")
L_R = float("-inf")
R_L = float("inf")
R_R = float("-inf")

LR_D = float("inf")
LR_U = float("-inf")
D_D = float("inf")
D_U = float("-inf")
U_D = float("inf")
U_U = float("-inf")

U = False
D = False
L = False
R = False

for i in range(N):

    x,y,d = input().split()

    x = int(x)
    y = int(y)

    if d == "L" or d == "R":
        LR_D = min(LR_D,y)
        LR_U = max(LR_U,y)

        if d == "L":

            L_L = min(L_L,x)
            L_R = max(L_R,x)
            L = True

        else: #R

            R_L = min(R_L,x)
            R_R = max(R_R,x)
            R = True

    if d == "D" or d == "U":

        UD_L = min(UD_L,x)
        UD_R = max(UD_R,x)

        if d == "D":

            D_D = min(D_D,y)
            D_U = max(D_U,y)
            D = True

        else: #U

            U_D = min(U_D,y)
            U_U = max(U_U,y)
            U = True

t0 = 0
t3 = 2 * 10 ** 8
last = float("inf")
ans = 1000000000000000000000

while abs(last - ans) > 10 ** (-100):

    t1 = Decimal((t0 * 2 + t3 * 1)) / Decimal(3)
    t2 = Decimal((t0 * 1 + t3 * 2)) / Decimal(3)

    #print (t1,t2,want(t1),want(t2))

    last = ans
    
    if want(t1) <= want(t2):
        ans = want(t1)
        t3 = t2

    else:
        ans = want(t2)
        t0 = t1

    #print (last,ans,t1,t2)

if ans <= 10 ** (-9):
    ans = 0
print(('{:.20g}'.format(ans)))


from itertools import combinations

INF = float("inf")
data = {d: [-INF, INF, -INF, INF] for d in 'RLUD'}

_, *XYD = open(0).read().split()
X = map(int, XYD[::3])
Y = map(int, XYD[1::3])
D = map(data.get, XYD[2::3])

for x, y, d in zip(X, Y, D):
    if d[0] < x:
        d[0] = x
    if d[1] > x:
        d[1] = x
    if d[2] < y:
        d[2] = y
    if d[3] > y:
        d[3] = y

X = [
    (data["L"][0], -1), (data["L"][1], -1),
    (data["R"][0], 1), (data["R"][1], 1),
    (data["U"][0], 0), (data["U"][1], 0),
    (data["D"][0], 0), (data["D"][1], 0),
]
Y = [
    (data["L"][2], 0), (data["L"][3], 0),
    (data["R"][2], 0), (data["R"][3], 0),
    (data["U"][2], 1), (data["U"][3], 1),
    (data["D"][2], -1), (data["D"][3], -1),
]

X = [(x, dx) for x, dx in X if abs(x) < INF]
Y = [(y, dy) for y, dy in Y if abs(y) < INF]

T = set(
    [0] +
    [max(0, (x - y) / (dy - dx)) for (x, dx), (y, dy) in combinations(X, 2) if dx != dy] +
    [max(0, (x - y) / (dy - dx)) for (x, dx), (y, dy) in combinations(Y, 2) if dx != dy]
)


def area(t):
    XX = [t * dx + x for x, dx in X]
    YY = [t * dy + y for y, dy in Y]

    dx = max(XX) - min(XX)
    dy = max(YY) - min(YY)

    return dx * dy


print(min(map(area, T)))

N = int(input())
xyd = [list(input().split()) for _ in range(N)]

def nasu(s, e, f, n, inf):
  L = [0] * 3
  a, b, c = inf, inf, inf
  for i in range(N):
    t = int(xyd[i][n])
    if xyd[i][2] == s:
      a = f(a, t)
    elif xyd[i][2] == e:
      b = f(b, t)
    else:
      c = f(c, t)
  L[0] = a
  if f(a, c) == a:
    L[1] = abs(a - c)
  else:
    L[0], L[1] = c, 0
  if f(L[0], b) != b:
    if f(c, b) == c:
      L[2] = abs(b - c)
      if L[1] > L[2]:
        L[2] = abs(a - b) / 2
        L[1] = L[2]
    else:
      L[2] = abs(a - b) / 2
      L[1] = L[2]
  else:
    L = [b, 0, 0]
  for i in range(3):
    if abs(L[i]) > abs(inf) / 2:
      L[i] = abs(inf)
  return L

inf = 10 ** 10
R = nasu("L", "R", max, 0, -inf)
L = nasu("R", "L", min, 0, inf)
U = nasu("D", "U", max, 1, -inf)
D = nasu("U", "D", min, 1, inf)

def honya(x):
  r = honyaraka(R, x, 1)
  l = honyaraka(L, x, -1)
  u = honyaraka(U, x, 1)
  d = honyaraka(D, x, -1)
  return abs(r - l) * abs(u - d)

def honyaraka(X, x, f):
  a, b, c = X
  if x <= b:
    return a + x * f * -1
  if x < c:
    return a + b * f * -1
  return a + b * f * -1 + (x - c) * f

ans = honya(0)
T = [R, L, U, D]
for i in range(4):
  for j in range(1, 3):
    x = T[i][j]
    if x != inf:
      ans = min(ans, honya(x))

print(ans)


import numpy as np

N = int(input())

x_min = [np.inf] * 4
x_max = [-np.inf] * 4
y_min = [np.inf] * 4
y_max = [-np.inf] * 4
for _ in range(N):
    x, y, d = input().split()
    x = int(x)
    y = int(y)
    i = {'R': 0, 'L': 1, 'U': 2, 'D': 3}[d]
    x_min[i] = min(x_min[i], x)
    x_max[i] = max(x_max[i], x)
    y_min[i] = min(y_min[i], y)
    y_max[i] = max(y_max[i], y)

x_max_ = max(x_max[2], x_max[3])
x_min_ = min(x_min[2], x_min[3])
y_max_ = max(y_max[0], y_max[1])
y_min_ = min(y_min[0], y_min[1])

def W(t):
    R = max(x_max[0] + t, x_max[1] - t, x_max_)
    L = min(x_min[0] + t, x_min[1] - t, x_min_)
    return R - L

def H(t):
    U = max(y_max[2] + t, y_max[3] - t, y_max_)
    D = min(y_min[2] + t, y_min[3] - t, y_min_)
    return U - D

def WH(t):
    return W(t) * H(t)

ts = [
    0,
    (x_max[1] - x_max[0]) / 2,
    (x_min[1] - x_min[0]) / 2,
    (y_max[3] - y_max[2]) / 2,
    (y_min[3] - y_min[2]) / 2,
    x_max_ - x_max[0],
    -(x_max_ - x_max[1]),
    x_min_ - x_min[0],
    -(x_min_ - x_min[1]),
    y_max_ - y_max[2],
    -(y_max_ - y_max[3]),
    y_min_ - y_min[2],
    -(y_min_ - y_min[3]),
]

result = np.inf;
for t in ts:
    if t >= 0:
        result = min(result, WH(t))

print(result)


from scipy.optimize import fmin
N = int(input())

INF = 10 ** 18
X = [[],[],[]]
Y = [[],[],[]]

for _ in range(N):
  x,y,d = input().split()
  x,y = int(x),int(y)
  if d == 'L':
    X[-1].append(x)
    Y[0].append(y)
  elif d == 'R':
    X[1].append(x)
    Y[0].append(y)
  elif d == 'U':
    Y[1].append(y)
    X[0].append(x)
  else:
    Y[-1].append(y)
    X[0].append(x)

for i in [-1,0,1]:
  X[i] = [min(X[i] + [INF]), max(X[i] + [-INF])]
  Y[i] = [min(Y[i] + [INF]), max(Y[i] + [-INF])]

def calc_width(t, X):
  left = INF
  right = -INF
  for i in [-1,0,1]:
    left = min(left, X[i][0] + i * t)
    right = max(right, X[i][1] + i * t)
  return right - left

def area(t):
  if t < 0:
    return INF
  return calc_width(t, X) * calc_width(t, Y)

xopt = fmin(area, x0 = 10**8, ftol = 10**-9, disp = False)
answer = area(xopt[0])
print(answer)


import sys
from scipy.optimize import fmin

input = sys.stdin.readline

n = int(input())

XR = []
XL = []
XS = []
YU = []
YD = []
YS = []

for _ in range(n):
    x, y, d = input().split()
    x = int(x)
    y = int(y)
    if d == "D":
        XS.append(x)
        YD.append(y)
    elif d == "U":
        XS.append(x)
        YU.append(y)
    elif d == "R":
        XR.append(x)
        YS.append(y)
    elif d == "L":
        XL.append(x)
        YS.append(y)


max_YD = max(YD + [float("-inf")])
max_YS = max(YS + [float("-inf")])
max_YU = max(YU + [float("-inf")])
min_YD = min(YD + [float("inf")])
min_YS = min(YS + [float("inf")])
min_YU = min(YU + [float("inf")])

max_XR = max(XR + [float("-inf")])
max_XL = max(XL + [float("-inf")])
max_XS = max(XS + [float("-inf")])
min_XR = min(XR + [float("inf")])
min_XL = min(XL + [float("inf")])
min_XS = min(XS + [float("inf")])


def diff_xy(t):
    diff_y = max(max_YD - t, max_YU + t, max_YS) - min(min_YD - t, min_YU + t, min_YS)
    diff_x = max(max_XL - t, max_XR + t, max_XS) - min(min_XL - t, min_XR + t, min_XS)
    return diff_x * diff_y


options = [
    max_YD - max_YS,
    max_YS - max_YU,
    (max_YD - max_YU) / 2,
    min_YD - min_YS,
    (min_YD - min_YU) / 2,
    min_YS - min_YU,
    max_XL - max_XS,
    max_XS - max_XR,
    (max_XL - max_XR) / 2,
    min_XL - min_XS,
    (min_XL - min_XR) / 2,
    min_XS - min_XR]

ans = diff_xy(0)

for option in options:
    if option >= 0:
        ans = min(ans, diff_xy(option))

print(ans)


import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 9
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N = II()
    xp9, xm9, xf9, yp9, ym9, yf9 = [-INF] * 6
    xp0, xm0, xf0, yp0, ym0, yf0 = [INF] * 6
    for _ in range(N):
        x, y, d = LS()
        x = int(x)
        y = int(y)
        if d == 'R':
            xp9 = max(xp9, x)
            xp0 = min(xp0, x)
            yf9 = max(yf9, y)
            yf0 = min(yf0, y)
        elif d == 'L':
            xm9 = max(xm9, x)
            xm0 = min(xm0, x)
            yf9 = max(yf9, y)
            yf0 = min(yf0, y)
        elif d == 'U':
            xf9 = max(xf9, x)
            xf0 = min(xf0, x)
            yp9 = max(yp9, y)
            yp0 = min(yp0, y)
        elif d == 'D':
            xf9 = max(xf9, x)
            xf0 = min(xf0, x)
            ym9 = max(ym9, y)
            ym0 = min(ym0, y)
    ts = [0]
    ts += [xf0 - xp0, xf9 - xp0, xf0 - xp9, xf9 - xp9]
    ts += [(xm0 - xp0) * 0.5, (xm9 - xp0) * 0.5, (xm0 - xp9) * 0.5, (xm9 - xp9) * 0.5]
    ts += [xm0 - xf0, xm9 - xf0, xm0 - xf9, xm9 - xf9]
    ts += [yf0 - yp0, yf9 - yp0, yf0 - yp9, yf9 - yp9]
    ts += [(ym0 - yp0) * 0.5, (ym9 - yp0) * 0.5, (ym0 - yp9) * 0.5, (ym9 - yp9) * 0.5]
    ts += [ym0 - yf0, ym9 - yf0, ym0 - yf9, ym9 - yf9]
    ts = [t for t in ts if t >= 0]
    ans = 10 ** 18
    for t in ts:
        xmax = max(xf9, xm9 - t, xp9 + t)
        xmin = min(xf0, xm0 - t, xp0 + t)
        ymax = max(yf9, ym9 - t, yp9 + t)
        ymin = min(yf0, ym0 - t, yp0 + t)
        tmp = (xmax - xmin) * (ymax - ymin)
        ans = min(ans, tmp)

    return ans

print(main())

# coding: utf-8
# Your code here!

import sys
n = int(input())
inf = float("inf")
xmin = [inf, inf, inf] #傾き-1,0,1
xmax = [-inf, -inf, -inf]
ymin = [inf, inf, inf]
ymax = [-inf, -inf, -inf]

for _ in range(n):
    x,y,d = [i for i in input().split()]
    x=int(x); y=int(y)
    if d=="U": ud = 2; lr = 1
    if d=="D": ud = 0; lr = 1
    if d=="L": ud = 1; lr = 0
    if d=="R": ud = 1; lr = 2
    xmin[lr] = min(xmin[lr],x)
    xmax[lr] = max(xmax[lr],x)
    ymin[ud] = min(ymin[ud],y)
    ymax[ud] = max(ymax[ud],y)

def lpos(t):
    return min([(v-1)*t + i for v,i in enumerate(xmin)])
def rpos(t):
    return max([(v-1)*t + i for v,i in enumerate(xmax)])
def dpos(t):
    return min([(v-1)*t + i for v,i in enumerate(ymin)])
def upos(t):
    return max([(v-1)*t + i for v,i in enumerate(ymax)])


s = {0}
for i in range(3):
    for j in range(i+1,3):
        t = (xmin[j]-xmin[i])/(i-j)
        if t > 0 and t != inf and t!= -inf: s.add(t)
        t = (xmax[j]-xmax[i])/(i-j)
        if 0 < t and t != inf and t!= -inf: s.add(t)
        t = (ymin[j]-ymin[i])/(i-j)
        if 0 < t and t != inf and t!= -inf: s.add(t)
        t = (ymax[j]-ymax[i])/(i-j)
        if 0 < t and t != inf and t!= -inf: s.add(t)
        

ans = 10**18
for t in s:
    area = (rpos(t)-lpos(t))*(upos(t)-dpos(t))
    if area < ans: ans = area

print(ans)

from collections import defaultdict
N=int(input())

xdic=defaultdict(set)
ydic=defaultdict(set)
for i in range(N):
  xs,ys,d=input().split()
  x=int(xs)
  y=int(ys)
  if d=="L":
    xdic[-1].add(x)
    ydic[0].add(y)
  elif d=="R":
    xdic[1].add(x)
    ydic[0].add(y)
  elif d=="U":
    xdic[0].add(x)
    ydic[1].add(y)
  else:
    xdic[0].add(x)
    ydic[-1].add(y)

xset=set()
for d in [-1,0,1]:
  if len(xdic[d]):
    min_d=min(xdic[d])
    max_d=max(xdic[d])
    xset.add((min_d,d))
    xset.add((max_d,d))
  
yset=set()
for d in [-1,0,1]:
  if len(ydic[d]):
    min_d=min(ydic[d])    
    max_d=max(ydic[d])
    yset.add((min_d,d))
    yset.add((max_d,d))

def cand_time(plist):
  ret=set()
  for i in range(len(plist)):
    p1,d1=plist[i]
    for j in range(i+1,len(plist)):
      p2,d2=plist[j]
      if d1==d2:
        continue
        
      if d1==-1:
        if d2==0:
          t=p1-p2
        else:
          t=(p1-p2)/2
      elif d1==0:
        if d2==-1:
          t=p2-p1
        else:
          t=p1-p2
      else:
        if d2==-1:
          t=(p2-p1)/2
        else:
          t=p2-p1
       
      if t>0:
        ret.add(t)
  return ret

cand_time_x=cand_time(list(xset))
cand_time_y=cand_time(list(yset))
#print(cand_time_x,cand_time_y)
cand_t=[0]+list(cand_time_x)+list(cand_time_y)
#print(cand_t)

def get_pos(pd,t):
  p,d=pd
  return p+d*t

answer=float("inf")
for t in cand_t:
  pos_min_x=float("inf")
  pos_max_x=-float("inf")
  for x2 in xset:
    pos_min_x=min(pos_min_x,get_pos(x2,t))
    pos_max_x=max(pos_max_x,get_pos(x2,t))
    
  pos_min_y=float("inf")
  pos_max_y=-float("inf")
  for y2 in yset:
    pos_min_y=min(pos_min_y,get_pos(y2,t))
    pos_max_y=max(pos_max_y,get_pos(y2,t))

  #print(t,pos_min_x,pos_max_x,pos_min_y,pos_max_y)
  t_ans=abs(pos_max_x-pos_min_x)*abs(pos_max_y-pos_min_y)
  if answer>=t_ans:
    answer=t_ans
    #print(answer,t,abs(pos_max_x-pos_min_x),abs(pos_max_y-pos_min_y))
  
print(answer)

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    aa = [LS() for _ in range(n)]
    xi = collections.defaultdict(lambda: inf)
    xa = collections.defaultdict(lambda: -inf)
    yi = collections.defaultdict(lambda: inf)
    ya = collections.defaultdict(lambda: -inf)
    km = 0
    for x,y,d in aa:
        x = int(x)
        y = int(y)
        if km < abs(x):
            km = abs(x)
        if km < abs(y):
            km = abs(y)
        if xi[d] > x:
            xi[d] = x
        if xa[d] < x:
            xa[d] = x
        if yi[d] > y:
            yi[d] = y
        if ya[d] < y:
            ya[d] = y

    ts = set([0])

    for d in [xi,xa,yi,ya]:
        ks = list(d.keys())
        for k in ks:
            for e in ks:
                ts.add(abs(d[k] - d[e]))
                ts.add(abs(d[k] - d[e]) / 2)

    def f(i):
        xxi = inf
        xxa = -inf
        yyi = inf
        yya = -inf
        for d,x in xi.items():
            if d == 'L':
                x -= i
            elif d == 'R':
                x += i
            if xxi > x:
                xxi = x
        for d,x in xa.items():
            if d == 'L':
                x -= i
            elif d == 'R':
                x += i
            if xxa < x:
                xxa = x
        for d,y in yi.items():
            if d == 'D':
                y -= i
            elif d == 'U':
                y += i
            if yyi > y:
                yyi = y
        for d,y in ya.items():
            if d == 'D':
                y -= i
            elif d == 'U':
                y += i
            if yya < y:
                yya = y

        return (xxa-xxi) * (yya-yyi)

    r = f(0)
    for i in ts:
        t = f(i)
        if r > t:
            r = t

    return '{:0.3f}'.format(r)


print(main())



def men(t):
    xmin = min(st + i * t for i, st in enumerate(mg[0]))
    xmax = max(st + i * t for i, st in enumerate(mg[1]))
    ymin = min(st + i * t for i, st in enumerate(ue[0]))
    ymax = max(st + i * t for i, st in enumerate(ue[1]))
    return (xmax - xmin) * (ymax - ymin)

n = int(input())
inf = 10**9
mg = [[inf, inf, inf], [-inf, -inf, -inf]]
ue = [[inf, inf, inf], [-inf, -inf, -inf]]
mg0=mg[0]
mg1=mg[1]
ue0=ue[0]
ue1=ue[1]
for _ in range(n):
    x, y, d = input().split()
    x = int(x)
    y = int(y)
    if d == "U":
        mv = 1
        uv = 2
    elif d == "D":
        mv = 1
        uv = 0
    elif d == "R":
        mv = 2
        uv = 1
    else:
        mv = 0
        uv = 1
    if x < mg0[mv]: mg0[mv] = x
    if x > mg1[mv]: mg1[mv] = x
    if y < ue0[uv]: ue0[uv] = y
    if y > ue1[uv]: ue1[uv] = y
t=set([0])
for lst in [mg0,mg1,ue0,ue1]:
    v0,v1,v2=lst
    for tk in [v0-v1,v1-v2,(v0-v2)/2]:
        if tk>=0:
            t.add(tk)
print(min(men(tk) for tk in t))

import itertools

def enum(a):
    t = [0]
    for a1, a2 in itertools.combinations(a, 2):
        t.append(a1[0]-a2[0])
        t.append(a2[0]-a1[0])
        t.append((a1[0]-a2[0])/2)
        t.append((a2[0]-a1[0])/2)
    return t

def calcWidth(l, t):
    x_min = x_max = l[0][0] + l[0][1] * t
    for item in l:
        x_min = min(x_min, item[0] + item[1] * t)
        x_max = max(x_max, item[0] + item[1] * t)
    return x_max - x_min

def calc(x_trip, y_trip, t):
    if t < 0:
        return calcWidth(x_trip, 0) * calcWidth(y_trip, 0)
    return calcWidth(x_trip, t) * calcWidth(y_trip, t)

n = int(input())
x_r, x_n, x_l = [], [], []
y_u, y_n, y_d = [], [], []
for _ in range(n):
    x, y, d = input().strip().split()
    x, y = int(x), int(y)
    if d == "R":
        x_r.append(x)
    elif d == "L":
        x_l.append(x)
    else:
        x_n.append(x)

    if d == "U":
        y_u.append(y)
    elif d == "D":
        y_d.append(y)
    else:
        y_n.append(y)

x_r.sort()
x_n.sort()
x_l.sort()
y_u.sort()
y_n.sort()
y_d.sort()

def ht(x, d):
    if len(x) > 0:
        return [(x[0], d), (x[-1], d)]
    return []
x_list = ht(x_r, 1) + ht(x_n, 0) + ht(x_l, -1)
y_list = ht(y_u, 1) + ht(y_n, 0) + ht(y_d, -1)
t = enum(x_list + y_list)

ans = calc(x_list, y_list, 0)
for t1 in t:
    if t1 < 0:
        continue
    wx = calcWidth(x_list, t1)
    wy = calcWidth(y_list, t1)
    ans = min(ans, calc(x_list, y_list, t1))
    ans = min(ans, calc(x_list, y_list, t1 + (wx-wy)/2))
    ans = min(ans, calc(x_list, y_list, t1 + (wy-wx)/2))
    ans = min(ans, calc(x_list, y_list, t1 + (wx*2-wy)/4))
    ans = min(ans, calc(x_list, y_list, t1 + (wx-wy*2)/4))
    ans = min(ans, calc(x_list, y_list, t1 + (wy*2-wx)/4))
    ans = min(ans, calc(x_list, y_list, t1 + (wy-wx*2)/4))
    ans = min(ans, calc(x_list, y_list, t1 + (wx*2-wy*2)/8))
    ans = min(ans, calc(x_list, y_list, t1 + (wy*2-wx*2)/8))
print(ans)



def main():
    R_edge, L_edge, U_edge, D_edge = [None]*3, [None]*3, [None]*3, [None]*3
    n = int(input())
    xyd = [input().split() for _ in [0]*n]
    xyd = [(int(x), int(y), d) for x, y, d in xyd]
    for x, y, d in xyd:
        if d in ["R", "L"]:
            if U_edge[1] is None:
                U_edge[1] = y
            else:
                U_edge[1] = max(U_edge[1], y)
            if D_edge[1] is None:
                D_edge[1] = y
            else:
                D_edge[1] = min(D_edge[1], y)
        else:
            if R_edge[1] is None:
                R_edge[1] = x
            else:
                R_edge[1] = max(R_edge[1], x)
            if L_edge[1] is None:
                L_edge[1] = x
            else:
                L_edge[1] = min(L_edge[1], x)
        for p, q, r in [[R_edge, "R", x], [L_edge, "L", x], [U_edge, "U", y], [D_edge, "D", y]]:
            if d == q:
                if p[0] is None:
                    p[0] = r
                    p[2] = r
                else:
                    p[0] = min(p[0], r)
                    p[2] = max(p[2], r)

    def area(t):
        RL, UD = [], []
        if R_edge[0] is not None:
            RL += [t+R_edge[0], t+R_edge[2]]
        if R_edge[1] is not None:
            RL += [R_edge[1]]
        if L_edge[0] is not None:
            RL += [-t+L_edge[0], -t+L_edge[2]]
        if L_edge[1] is not None:
            RL += [L_edge[1]]
        if U_edge[0] is not None:
            UD += [t+U_edge[0], t+U_edge[2]]
        if U_edge[1] is not None:
            UD += [U_edge[1]]
        if D_edge[0] is not None:
            UD += [-t+D_edge[0], -t+D_edge[2]]
        if D_edge[1] is not None:
            UD += [D_edge[1]]
        if len(RL)*len(UD) == 0:
            return 0
        else:
            return (max(RL)-min(RL))*(max(UD)-min(UD))

    t = [0]
    for edge in [R_edge, L_edge, U_edge, D_edge]:
        if None not in edge:
            t.append(abs(edge[1]-edge[0]))
            t.append(abs(edge[1]-edge[2]))
    for edge1, edge2 in [[R_edge, L_edge], [U_edge, D_edge]]:
        if None not in [edge1[1], edge2[0]]:
            t.append(abs(edge1[1]-edge2[0]))
            t.append(abs(edge1[1]-edge2[2]))
        if None not in [edge2[1], edge1[0]]:
            t.append(abs(edge2[1]-edge1[0]))
            t.append(abs(edge2[1]-edge1[2]))
        if None not in [edge1[0], edge2[0]]:
            for i in [0, 2]:
                for j in [0, 2]:
                    t.append(abs(edge2[i]-edge1[j])/2)

    print((min([area(i) for i in t])))


main()


N = int(input())
 
PS = [[], [], [], []]
S = "RLUD".index
 
for i in range(N):
    x, y, d = input().split(); x = int(x); y = int(y)
    PS[S(d)].append((x, y))
 
T = [0]
INF = 10**9
 
dymin = INF; dymax = -INF
P = []
for i in [0, 1]:
    xmin = INF; xmax = -INF
    for x, y in PS[i]:
        dymin = min(dymin, y)
        dymax = max(dymax, y)
        xmin = min(xmin, x)
        xmax = max(xmax, x)
    P.append((xmin, xmax))
for x0 in P[0]:
    for x1 in P[1]:
        T.append(max(x1 - x0, 0) / 2.)
 
dxmin = INF; dxmax = -INF
Q = []
for i in [2, 3]:
    ymin = INF; ymax = -INF
    for x, y in PS[i]:
        dxmin = min(dxmin, x)
        dxmax = max(dxmax, x)
        ymin = min(ymin, y)
        ymax = max(ymax, y)
    Q.append((ymin, ymax))
for y0 in Q[0]:
    for y1 in Q[1]:
        T.append(max(y1 - y0, 0) / 2.)
 
for x0 in [dxmin, dxmax]:
    for x in P[0]:
        T.append(max(x0 - x, 0))
    for x in P[1]:
        T.append(max(x - x0, 0))
for y0 in [dymin, dymax]:
    for y in Q[0]:
        T.append(max(y0 - y, 0))
    for y in Q[1]:
        T.append(max(y - y0, 0))
 
ans = 10**30
for t in T:
    xmin = dxmin; xmax = dxmax
    ymin = dymin; ymax = dymax
 
    xi, xa = P[0]
    if xi != INF:
        xmin = min(xmin, xi+t)
        xmax = max(xmax, xa+t)
    xi, xa = P[1]
    if xi != INF:
        xmin = min(xmin, xi-t)
        xmax = max(xmax, xa-t)
    yi, ya = Q[0]
    if yi != INF:
        ymin = min(ymin, yi+t)
        ymax = max(ymax, ya+t)
    yi, ya = Q[1]
    if yi != INF:
        ymin = min(ymin, yi-t)
        ymax = max(ymax, ya-t)
    ans = min(ans, (xmax - xmin) * (ymax - ymin))
print("%.6f" % ans)

N = int(input())
M = {'R': [], 'L':[], 'U': [], 'D': [], 'X': [], 'Y': []}
for _ in range(N):
  x, y, d = input().split()
  if d in ['R', 'L']:
    M[d].append(int(x))
    M['Y'].append(int(y))
  else:
    M['X'].append(int(x))
    M[d].append(int(y))
for d in 'RLDUXY':
  M[d] = sorted(M[d])
T = [0] * 13
T[0] = M['X'][0] - M['R'][0] if M['X'] and M['R'] else -1
T[1] = M['L'][0] - M['X'][0] if M['X'] and M['L'] else -1
T[2] = (M['L'][0] - M['R'][0]) / 2 if M['L'] and M['R'] else -1
T[3] = M['X'][-1] - M['R'][-1] if M['X'] and M['R'] else -1
T[4] = M['L'][-1] - M['X'][-1] if M['X'] and M['L'] else -1
T[5] = (M['L'][-1] - M['R'][-1]) / 2 if M['L'] and M['R'] else -1
T[6] = M['Y'][-1] - M['U'][-1] if M['Y'] and M['U'] else -1
T[7] = M['D'][-1] - M['Y'][-1] if M['Y'] and M['D'] else -1
T[8] = (M['D'][-1] - M['U'][-1]) / 2 if M['D'] and M['U'] else -1
T[9] = M['Y'][0] - M['U'][0] if M['Y'] and M['U'] else -1
T[10] = M['D'][0] - M['Y'][0] if M['Y'] and M['D'] else -1
T[11] = (M['D'][0] - M['U'][0]) / 2 if M['D'] and M['U'] else -1
Rect = [-1] * 13
for i, t in enumerate(T):
  if t < 0:
    continue
  R = []
  L = []
  U = []
  D = []
  if M['R']:
    R.append(M['R'][-1] + t)
    L.append(M['R'][0] + t)
  if M['L']:
    R.append(M['L'][-1] - t)
    L.append(M['L'][0] - t)
  if M['U']:
    U.append(M['U'][-1] + t)
    D.append(M['U'][0] + t)
  if M['D']:
    U.append(M['D'][-1] - t)
    D.append(M['D'][0] - t)
  if M['X']:
    R.append(M['X'][-1])
    L.append(M['X'][0])
  if M['Y']:
    U.append(M['Y'][-1])
    D.append(M['Y'][0])
  Rect[i] = (max(R) - min(L)) * (max(U) - min(D))
print(min([r for r in Rect if r >= 0]))

INF = float('inf')

N = int(input())

xConstMin, xConstMax = INF, -INF
xAscMin, xAscMax = INF, -INF
xDescMin, xDescMax = INF, -INF
yConstMin, yConstMax = INF, -INF
yAscMin, yAscMax = INF, -INF
yDescMin, yDescMax = INF, -INF
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    if d == 'R':
        xAscMax = max(xAscMax, x)
        xAscMin = min(xAscMin, x)
        yConstMax = max(yConstMax, y)
        yConstMin = min(yConstMin, y)
    elif d == 'L':
        xDescMax = max(xDescMax, x)
        xDescMin = min(xDescMin, x)
        yConstMax = max(yConstMax, y)
        yConstMin = min(yConstMin, y)
    elif d == 'U':
        xConstMax = max(xConstMax, x)
        xConstMin = min(xConstMin, x)
        yAscMax = max(yAscMax, y)
        yAscMin = min(yAscMin, y)
    elif d == 'D':
        xConstMax = max(xConstMax, x)
        xConstMin = min(xConstMin, x)
        yDescMax = max(yDescMax, y)
        yDescMin = min(yDescMin, y)

tms = []

t1 = max(0, xDescMax - xConstMax)
t2 = max(0, xConstMax - xAscMax)
if t1 >= t2:
    t = max(0, (xDescMax-xAscMax)/2)
    tms.append(t)
else:
    tms.append(t1)
    tms.append(t2)

t1 = max(0, xConstMin - xAscMin)
t2 = max(0, xDescMin - xConstMin)
if t1 >= t2:
    t = max(0, (xDescMin-xAscMin)/2)
    tms.append(t)
else:
    tms.append(t1)
    tms.append(t2)

t1 = max(0, yDescMax - yConstMax)
t2 = max(0, yConstMax - yAscMax)
if t1 >= t2:
    t = max(0, (yDescMax-yAscMax)/2)
    tms.append(t)
else:
    tms.append(t1)
    tms.append(t2)

t1 = max(0, yConstMin - yAscMin)
t2 = max(0, yDescMin - yConstMin)
if t1 >= t2:
    t = max(0, (yDescMin-yAscMin)/2)
    tms.append(t)
else:
    tms.append(t1)
    tms.append(t2)

ans = INF
for tm in tms:
    if tm == INF: continue

    xs = [xConstMin, xConstMax, xAscMin+tm, xAscMax+tm, xDescMin-tm, xDescMax-tm]
    ys = [yConstMin, yConstMax, yAscMin+tm, yAscMax+tm, yDescMin-tm, yDescMax-tm]

    xMin, xMax = INF, -INF
    for x in xs:
        if x == INF or x == -INF: continue
        xMin = min(xMin, x)
        xMax = max(xMax, x)

    yMin, yMax = INF, -INF
    for y in ys:
        if y == INF or y == -INF: continue
        yMin = min(yMin, y)
        yMax = max(yMax, y)

    ans = min(ans, (xMax-xMin)*(yMax-yMin))

print(ans)


inf = float('inf')
N = int(input())
MRp = -inf
MR = -inf
MRm = -inf
mRp = inf
mR = inf
mRm = inf
MUp = -inf
MU = -inf
MUm = -inf
mUp = inf
mU = inf
mUm = inf

for i in range(N):
	x, y, d = input().split()
	x, y = int(x), int(y)
	if d == 'R':
		MRp = max(MRp, x)
		mRp = min(mRp, x)
		MU = max(MU, y)
		mU = min(mU, y)
	elif d == 'L':
		MRm = max(MRm, x)
		mRm = min(mRm, x)
		MU = max(MU, y)
		mU = min(mU, y)
	elif d == 'U':
		MUp = max(MUp, y)
		mUp = min(mUp, y)
		MR = max(MR, x)
		mR = min(mR, x)
	else:
		MUm = max(MUm, y)
		mUm = min(mUm, y)
		MR = max(MR, x)
		mR = min(mR, x)

t = [0]
if MR > MRp:
	t.append(MR - MRp)
if MRm > MRp:
	t.append((MRm - MRp) / 2)
if MRm > MR:
	t.append(MRm - MR)
if mRm > mR:
	t.append(mRm - mR)
if mRm > mRp:
	t.append((mRm - mRp) / 2)
if mR > mRp:
	t.append(mR - mRp)
if MU > MUp:
	t.append(MU - MUp)
if MUm > MUp:
	t.append((MUm - MUp) / 2)
if MUm > MU:
	t.append(MUm - MU)
if mUm > mU:
	t.append(mUm - mU)
if mUm > mUp:
	t.append((mUm - mUp) / 2)
if mU > mUp:
	t.append(mU - mUp)

ans = inf
for i in t:
	dx = max(MRp + i, MR, MRm - i) - min(mRp + i, mR, mRm - i)
	dy = max(MUp + i, MU, MUm - i) - min(mUp + i, mU, mUm - i)
	ans = min(ans, dx * dy)
print(ans)

from scipy.optimize import fmin
N = int(input())

INF = 10 ** 18
# x 方向に動かない点、右移動の点、左移動の点の最小・最大値
fixed_x = [INF, -INF]
R = [INF, -INF]
L = [INF, -INF]
# y 方向に動かない点、右移動の点、左移動の点の最小・最大値
fixed_y = [INF, -INF]
U = [INF, -INF]
D = [INF, -INF]

def update(fixed, li, x, y):
  li[0], li[1] = min(li[0], x), max(li[1], x)
  fixed[0], fixed[1] = min(fixed[0], y), max(fixed[1], y)
  
for _ in range(N):
  x,y,d = input().split()
  x,y = int(x), int(y)
  if d == 'L':
    update(fixed_y, L, x, y)
  elif d == 'R':
    update(fixed_y, R, x, y)
  elif d == 'U':
    update(fixed_x, U, y, x)
  else:
    update(fixed_x, D, y, x)

def calc_x(t, fixed, dec, inc):
  left = INF
  right = -INF
  for li, speed in [(fixed, 0), (dec, -1), (inc, 1)]:
    left = min(left, li[0] + speed * t)
    right = max(right, li[1] + speed * t)
  return right - left

def area(t):
  if t < 0:
    return INF
  return calc_x(t, fixed_x, L, R) * calc_x(t, fixed_y, D, U)

xopt = fmin(area, x0 = 10**8, ftol = 10**-9, disp = False)
answer = area(xopt[0])
print(answer)


N = int(input())
x1, x2, y1, y2 = {}, {}, {}, {}
INF = 10 ** 10

for i in range(N):
    x, y, d = input().split()
    x, y = int(x) * 2, int(y) * 2

    def update_x(v, x):
        if v not in x1:
            x1[v] = x2[v] = x
        else:
            x1[v] = min(x1[v], x)
            x2[v] = max(x2[v], x)

    def update_y(v, y):
        if v not in y1:
            y1[v] = y2[v] = y
        else:
            y1[v] = min(y1[v], y)
            y2[v] = max(y2[v], y)

    if d == 'R':
        update_x(+1, x)
        update_y(0, y)
    elif d == 'L':
        update_x(-1, x)
        update_y(0, y)
    elif d == 'U':
        update_x(0, x)
        update_y(+1, y)
    elif d == 'D':
        update_x(0, x)
        update_y(-1, y)

def area(t):
    xmin, xmax, ymin, ymax = INF, -INF, INF, -INF
    for (v, x) in list(x1.items()):
        xmin = min(xmin, x + v * t)
    for (v, x) in list(x2.items()):
        xmax = max(xmax, x + v * t)
    for (v, y) in list(y1.items()):
        ymin = min(ymin, y + v * t)
    for (v, y) in list(y2.items()):
        ymax = max(ymax, y + v * t)
    return (xmax - xmin) * (ymax - ymin)

ans = area(0)

x3 = list(x1.items()) + list(x2.items())
for i in range(len(x3)):
    for j in range(i + 1, len(x3)):
        if x3[i][0] != x3[j][0]:
            t = (x3[j][1] - x3[i][1]) // (x3[i][0] - x3[j][0])
            if t >= 0:
                ans = min(ans, area(t))

y3 = list(y1.items()) + list(y2.items())
for i in range(len(y3)):
    for j in range(i + 1, len(y3)):
        if y3[i][0] != y3[j][0]:
            t = (y3[j][1] - y3[i][1]) // (y3[i][0] - y3[j][0])
            if t >= 0:
                ans = min(ans, area(t))

print((ans / 4))


import sys
from scipy.optimize import fmin

input = sys.stdin.readline

n = int(input())

XR = []
XL = []
XS = []
YU = []
YD = []
YS = []

for _ in range(n):
    x, y, d = input().split()
    x = int(x)
    y = int(y)
    if d == "D":
        XS.append(x)
        YD.append(y)
    elif d == "U":
        XS.append(x)
        YU.append(y)
    elif d == "R":
        XR.append(x)
        YS.append(y)
    elif d == "L":
        XL.append(x)
        YS.append(y)

max_YD = max(YD + [float("-inf")])
max_YS = max(YS + [float("-inf")])
max_YU = max(YU + [float("-inf")])
min_YD = min(YD + [float("inf")])
min_YS = min(YS + [float("inf")])
min_YU = min(YU + [float("inf")])

max_XR = max(XR + [float("-inf")])
max_XL = max(XL + [float("-inf")])
max_XS = max(XS + [float("-inf")])
min_XR = min(XR + [float("inf")])
min_XL = min(XL + [float("inf")])
min_XS = min(XS + [float("inf")])


def diff_xy(t):
    if t < 0:
        return float("inf")
    diff_y = max(max_YD - t, max_YU + t, max_YS) - min(min_YD - t, min_YU + t, min_YS)
    diff_x = max(max_XL - t, max_XR + t, max_XS) - min(min_XL - t, min_XR + t, min_XS)
    return diff_x * diff_y


def binary_search(min_t, max_t):
    mid_t = (min_t + max_t) / 2
    if max_t - min_t < 10 ** (-10):
        return diff_xy(mid_t)

    if diff_xy(min_t) < diff_xy(mid_t):
        return binary_search(min_t, mid_t)
    elif diff_xy(max_t) < diff_xy(mid_t):
        return binary_search(mid_t, max_t)
    else:
        return opt(min_t, mid_t, max_t)


def opt(a, b, c):
    optimal_a = fmin(diff_xy, a, full_output=False, disp=False, xtol=10 ** (-10))
    optimal_b = fmin(diff_xy, b, full_output=False, disp=False, xtol=10 ** (-10))
    optimal_c = fmin(diff_xy, c, full_output=False, disp=False, xtol=10 ** (-10))
    ans = min(diff_xy(optimal_a[0]), diff_xy(optimal_b[0]), diff_xy(optimal_c[0]))
    return (ans)


print(binary_search(0, 2 * 10 ** 8))

INF=10**20

import sys
import numpy as np

input=sys.stdin.readline

N=int(input())
direction=["U","D","R","L"]
X={moji:[] for moji in direction}
Y={moji:[] for moji in direction}
for i in range(N):
    x,y,d=input().split()
    x=int(x)
    y=int(y)
    X[d].append(x)
    Y[d].append(y)

query=[]
#Xmax
if not X["L"]:
    Lmax=-INF
else:
    Lmax=max(X["L"])
if not X["R"]:
    Rmax=-INF
else:
    Rmax=max(X["R"])
if not X["U"]:
    mobUmax=-INF
else:
    mobUmax=max(X["U"])
if not X["D"]:
    mobDmax=-INF
else:
    mobDmax=max(X["D"])
UDmax=max(mobUmax,mobDmax)

q1=(Lmax-Rmax)/2
q2=Lmax-UDmax
q3=UDmax-Rmax
if q1>q2:
    query.append([q2,"Xmax",0,UDmax])
    query.append([q3,"Xmax",1,Rmax])
else:
    query.append([q1,"Xmax",1,Rmax])

#Xmin
if not X["L"]:
    Lmin=INF
else:
    Lmin=min(X["L"])
if not X["R"]:
    Rmin=INF
else:
    Rmin=min(X["R"])
if not X["U"]:
    mobUmin=INF
else:
    mobUmin=min(X["U"])
if not X["D"]:
    mobDmin=INF
else:
    mobDmin=min(X["D"])
UDmin=min(mobUmin,mobDmin)


q1=(Lmin-Rmin)/2
q2=UDmin-Rmin
q3=Lmin-UDmin
if q1>q2:
    query.append([q2,"Xmin",0,UDmin])
    query.append([q3,"Xmin",-1,Lmin])
else:
    query.append([q1,"Xmin",-1,Lmin])

#Ymax
if not Y["L"]:
    mobLmax=-INF
else:
    mobLmax=max(Y["L"])
if not Y["R"]:
    mobRmax=-INF
else:
    mobRmax=max(Y["R"])
if not Y["U"]:
    Umax=-INF
else:
    Umax=max(Y["U"])
if not Y["D"]:
    Dmax=-INF
else:
    Dmax=max(Y["D"])
LRmax=max(mobLmax,mobRmax)


q1=(Dmax-Umax)/2
q2=Dmax-LRmax
q3=LRmax-Umax
if q1>q2:
    query.append([q2,"Ymax",0,LRmax])
    query.append([q3,"Ymax",1,Umax])
else:
    query.append([q1,"Ymax",1,Umax])

#Ymin
if not Y["L"]:
    mobLmin=INF
else:
    mobLmin=min(Y["L"])
if not Y["R"]:
    mobRmin=INF
else:
    mobRmin=min(Y["R"])
if not Y["U"]:
    Umin=INF
else:
    Umin=min(Y["U"])
if not Y["D"]:
    Dmin=INF
else:
    Dmin=min(Y["D"])
LRmin=min(mobLmin,mobRmin)

q1=(Dmin-Umin)/2
q2=LRmin-Umin
q3=Dmin-LRmin
if q1>q2:
    query.append([q2,"Ymin",0,UDmin])
    query.append([q3,"Ymin",-1,Dmin])
else:
    query.append([q1,"Xmax",-1,Dmin])

query.sort()
xmax=np.poly1d([-1,Lmax])
xmin=np.poly1d([1,Rmin])
ymax=np.poly1d([-1,Dmax])
ymin=np.poly1d([1,Umin])

val=[]
for i in range(-1,len(query)-1):
    if i==-1:
        p=(xmax-xmin)*(ymax-ymin)
        coef2d=p.coef[0]
        coef1d=p.coef[1]
        if coef2d>0:
            minval=coef1d/(2*coef2d)
            next=query[i+1][0]
            if minval>=0 and next>minval:
                val.append(minval)
    else:
        t,func,c2d,c1d=query[i]
        if func=="Xmax":
            xmax=np.poly1d([c2d,c1d])
        if func=="Xmin":
            xmin=np.poly1d([c2d,c1d])
        if func=="Ymax":
            ymax=np.poly1d([c2d,c1d])
        if func=="Ymin":
            ymin=np.poly1d([c2d,c1d])
        p=(xmax-xmin)*(ymax-ymin)
        if p.order==2:
            coef2d=p.coef[0]
            coef1d=p.coef[1]
            if coef2d>0:
                minval=coef1d/(2*coef2d)
                next=query[i+1][0]
                if minval>=0 and next>minval:
                    val.append(minval)
def Xmax(t):
    return max(UDmax,Rmax+t,Lmax-t)
def Xmin(t):
    return min(UDmin,Rmin+t,Lmin-t)
def Ymax(t):
    return max(LRmax,Umax+t,Dmax-t)
def Ymin(t):
    return min(LRmin,Umin+t,Dmin-t)

def function(t):
    return (Xmax(t)-Xmin(t))*(Ymax(t)-Ymin(t))

ans=function(0)
ppp=0
for i in range(0,len(val)):
    if 10**8>=val[i]>=0:
        if ans>function(val[i]):
            ans=min(ans,function(val[i]))
            ppp=val[i]

for i in range(0,len(query)):
    if 10**8>=query[i][0]>=0:
        if ans>function(query[i][0]):
            ans=min(ans,function(query[i][0]))
            ppp=query[i][0]

print(ans)

inf = float('inf')
from scipy.optimize import fmin
from collections import defaultdict
dir = {'R', 'L', 'U', 'D'}
N = int(input())
dic = defaultdict(list)
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    dic[d].append((x, y))
x_max = defaultdict(lambda : -inf)
x_min = defaultdict(lambda : inf)
y_max = defaultdict(lambda : -inf)
y_min = defaultdict(lambda : inf)
for d in dir:
    if dic[d]:
        dic[d].sort()
        x_max[d] = dic[d][-1][0]
        x_min[d] = dic[d][0][0]
        dic[d].sort(key = lambda x:x[1])
        y_max[d] = dic[d][-1][1]
        y_min[d] = dic[d][0][1]
def dx(t):
    return max(x_max['U'], x_max['D'], x_max['R']+t, x_max['L']-t)-min(x_min['U'], x_min['D'], x_min['R']+t, x_min['L']-t)
def dy(t):
    return max(y_max['U']+t, y_max['D']-t, y_max['R'], y_max['L'])-min(y_min['U']+t, y_min['D']-t, y_min['R'], y_min['L'])
def f(t):
    if t<0:
        return inf
    return dx(t)*dy(t)
def make_cand(s, d, i):
    return [abs(s-i), abs(d-i)/2, abs(s-d)]
cand = [0]+make_cand(max(x_max['U'], x_max['D']), x_max['R'], x_max['L'])               +make_cand(min(x_min['U'], x_min['D']), x_min['R'], x_min['L'])               +make_cand(max(y_max['R'], y_max['L']), y_max['U'], y_max['D'])               +make_cand(min(y_min['R'], y_min['L']), y_min['U'], y_min['D'])
ans = min(f(t)for t in cand)
print(ans)















INF = float('inf')
N = int(input())
d = {'R':[[],[]],'L':[[],[]],'U':[[],[]],'D':[[],[]]}
for i in range(N):
    x,y,f = input().split()
    x = int(x)
    y = int(y)
    d[f][0].append(x)
    d[f][1].append(y)

Ts = []

xM = max(max(d['U'][0]+[-INF]),max(d['D'][0]+[-INF]))
xMr = max(d['R'][0]+[-INF])
xMl = max(d['L'][0]+[-INF])

def xmax(T):
    return max(xM,xMr+T,xMl-T)

Ts += [max(0,xMl-xM),max(0,xM-xMr),max(0,(xMl-xMr)/2)]

xm = min(min(d['U'][0]+[INF]),min(d['D'][0]+[INF]))
xmr = min(d['R'][0]+[INF])
xml = min(d['L'][0]+[INF])

def xmin(T):
    return min(xm,xmr+T,xml-T)

Ts += [max(0,xml-xm),max(0,xm-xmr),max(0,(xml-xmr)/2)]

yM = max(max(d['R'][1]+[-INF]),max(d['L'][1]+[-INF]))
yMu = max(d['U'][1]+[-INF])
yMd = max(d['D'][1]+[-INF])

def ymax(T):
    return max(yM,yMu+T,yMd-T)

Ts += [max(0,yMd-yM),max(0,yM-yMu),max(0,(yMd-yMu)/2)]

ym = min(min(d['R'][1]+[INF]),min(d['L'][1]+[INF]))
ymu = min(d['U'][1]+[INF])
ymd = min(d['D'][1]+[INF])

def ymin(T):
    return min(ym,ymu+T,ymd-T)

Ts += [max(0,ymd-ym),max(0,ym-ymu),max(0,(ymd-ymu)/2)]

ans = INF

for T in Ts:
    ans = min(ans,(xmax(T)-xmin(T))*(ymax(T)-ymin(T)))

print(ans)

from decimal import *
getcontext().prec = 100
N = int(input())
Xmi, Xma, Ymi, Yma, DYmi, DYma, UYmi, UYma, RXmi, RXma, LXmi, LXma = [(10**10), -(10**10)] * 6
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    
    if d == "R":
        RXmi = min(RXmi, x)
        RXma = max(RXma, x)
    elif d == "L":
        LXmi = min(LXmi, x)
        LXma = max(LXma, x)
    else:
        Xmi = min(Xmi, x)
        Xma = max(Xma, x)
        
    if d == "U":
        UYmi = min(UYmi, y)
        UYma = max(UYma, y)
    elif d == "D":
        DYmi = min(DYmi, y)
        DYma = max(DYma, y)
    else:
        Ymi = min(Ymi, y)
        Yma = max(Yma, y)

def calc(t):
    xmi = min(RXmi+t, LXmi-t, Xmi)
    xma = max(RXma+t, LXma-t, Xma)
    ymi = min(UYmi+t, DYmi-t, Ymi)
    yma = max(UYma+t, DYma-t, Yma)
    return max(yma-ymi, 0)*max(xma-xmi, 0)
    
def dii(t):
    a = Decimal("0.00000001")
    return calc(t+a) - calc(t-a)

l = Decimal("0")
r = Decimal("10000000000")
for _ in range(500):
    m = (l+r)/2
    if dii(m) > 0:
        r = m
    else:
        l = m
print((calc(m)))


# coding: utf-8
# Your code here!

import sys
n = int(input())

inf = float("inf")
u=d=l=r=0
umin = inf
umax = -inf
dmin = inf
dmax = -inf
lmin = inf
lmax = -inf
rmin = inf
rmax = -inf
xmin = inf
xmax = -inf
ymin = inf
ymax = -inf
xx=yy=0

for j in range(n):
    x,y,D = [i for i in input().split()]
    x=int(x); y=int(y)
    if D == "U":
        umin = min(umin,y)
        umax = max(umax,y)
        u=1
        xmin = min(xmin,x)
        xmax = max(xmax,x)
        xx=1
    if D == "D":
        dmin = min(dmin,y)
        dmax = max(dmax,y)
        d=1
        xmin = min(xmin,x)
        xmax = max(xmax,x)
        xx=1
    if D == "L":
        lmin = min(lmin,x)
        lmax = max(lmax,x)
        l=1
        ymin = min(ymin,y)
        ymax = max(ymax,y)
        yy=1
    if D == "R":
        rmin = min(rmin,x)
        rmax = max(rmax,x)
        r=1
        ymin = min(ymin,y)
        ymax = max(ymax,y)
        yy=1

def lpos(t):
    ans = inf
    if xx: ans = min(ans,xmin)
    if l: ans = min(ans,lmin-t)
    if r: ans = min(ans,rmin+t)
    return ans
def rpos(t):
    ans = -inf
    if xx: ans = max(ans,xmax)
    if l: ans = max(ans,lmax-t)
    if r: ans = max(ans,rmax+t)
    return ans

def dpos(t):
    ans = inf
    if yy: ans = min(ans,ymin)
    if u: ans = min(ans,umin+t)
    if d: ans = min(ans,dmin-t)
    return ans
def upos(t):
    ans = -inf
    if yy: ans = max(ans,ymax)
    if u: ans = max(ans,umax+t)
    if d: ans = max(ans,dmax-t)
    return ans

s = {0}
if xx and l:
    if lmin - xmin > 0: s.add(lmin - xmin)
    if lmax - xmax > 0: s.add(lmax - xmax)
if xx and r:
    if xmin - rmin > 0: s.add(xmin - rmin)
    if xmax - rmax > 0: s.add(xmax - rmax)
if l and r:
    if lmin-rmin > 0: s.add((lmin-rmin)/2)
    if lmax-rmax > 0: s.add((lmax-rmax)/2)

if yy and d:
    if dmin - ymin > 0: s.add(dmin - ymin)
    if dmax - ymax > 0: s.add(dmax - ymax)
if yy and u:
    if ymin - umin > 0: s.add(ymin - umin)
    if ymax - umax > 0: s.add(ymax - umax)
if d and u:
    if dmin-umin > 0: s.add((dmin-umin)/2)
    if dmax-umax > 0: s.add((dmax-umax)/2)
    
#print(rmax,xmax)

ans = 10**18
for t in s:
#    print(rpos(t),lpos(t),dpos(t),upos(t),xmin,ymin,xmax,ymax,xx,yy)
    area = (rpos(t)-lpos(t))*(upos(t)-dpos(t))
#    print(t,area)
    if area < ans:
        ans = area

print(ans)