AtCoder Beginner Contest 130 - Minimum Bounding Box

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: MEDIUM_HARD

Starter code:

Solutions:
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)
xRmin = min(xR | {I})
xLmin = min(xL | {I})
xSmin = min(xS | {I})
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
yUmin = min(yU | {I})
yDmin = min(yD | {I})
ySmin = min(yS | {I})
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())
import sys
input = sys.stdin.readline
inf = 10 ** 20
dd = {'R': [-inf] * 3, 'L': [inf] * 3, 'U': [-inf] * 3, 'D': [inf] * 3}
for _ in range(N):
	(x, y, d) = input().split()
	(x, y) = (int(x), int(y))
	if d == 'R':
		dd['R'][0] = max(x, dd['R'][0])
		dd['L'][1] = min(x, dd['L'][1])
		dd['U'][2] = max(y, dd['U'][2])
		dd['D'][2] = min(y, dd['D'][2])
	elif d == 'L':
		dd['L'][0] = min(x, dd['L'][0])
		dd['R'][1] = max(x, dd['R'][1])
		dd['U'][2] = max(y, dd['U'][2])
		dd['D'][2] = min(y, dd['D'][2])
	elif d == 'U':
		dd['R'][2] = max(x, dd['R'][2])
		dd['L'][2] = min(x, dd['L'][2])
		dd['U'][0] = max(y, dd['U'][0])
		dd['D'][1] = min(y, dd['D'][1])
	elif d == 'D':
		dd['R'][2] = max(x, dd['R'][2])
		dd['L'][2] = min(x, dd['L'][2])
		dd['U'][1] = max(y, dd['U'][1])
		dd['D'][0] = min(y, dd['D'][0])
tls = []
for d in 'RLUD':
	m = -1 if d in 'RU' else 1
	t1 = -m * (dd[d][1] - dd[d][2])
	t2 = -m * (dd[d][2] - dd[d][0])
	t3 = m * float(dd[d][0] - dd[d][1]) / 2
	if t1 < t3 and t3 < t2:
		if t1 > 0:
			tls.append((0, m, dd[d][1], d))
		if t2 > 0:
			tls.append((max(0, t1), 0, dd[d][2], d))
		tls.append((max(0, t2), -m, dd[d][0], d))
	else:
		if t3 > 0:
			tls.append((0, m, dd[d][1], d))
		tls.append((max(0, t3), -m, dd[d][0], d))
tls.sort()
btl = 0
r = 10 ** 20
for (t, a, b, d) in tls:
	if btl > 10 ** 10:
		btl = inf
		break
	if t != btl:
		a1 = dd['R'][0] - dd['L'][0]
		a2 = dd['U'][0] - dd['D'][0]
		b1 = dd['R'][1] - dd['L'][1]
		b2 = dd['U'][1] - dd['D'][1]
		r = min(r, (a1 * t + b1) * (a2 * t + b2))
		r = min(r, (a1 * btl + b1) * (a2 * btl + b2))
	dd[d] = (a, b)
	btl = t
if btl < inf:
	t = inf
	a1 = dd['R'][0] - dd['L'][0]
	a2 = dd['U'][0] - dd['D'][0]
	b1 = dd['R'][1] - dd['L'][1]
	b2 = dd['U'][1] - dd['D'][1]
	r = min(r, (a1 * t + b1) * (a2 * t + b2))
	r = min(r, (a1 * btl + b1) * (a2 * btl + b2))
print(r)


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())


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):
	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):
	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)


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)
	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_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_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)
	last = ans
	if want(t1) <= want(t2):
		ans = want(t1)
		t3 = t2
	else:
		ans = want(t2)
		t0 = t1
if ans <= 10 ** (-9):
	ans = 0
print('{:.20g}'.format(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))


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]))


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) = map(int, (x, y))
	P[d].append((x, y))

def fst(x):
	return x[0]

def snd(x):
	return x[1]
inf = float('inf')
S = {d: {'xmin': min(map(fst, P[d]), default=inf), 'xmax': max(map(fst, P[d]), default=-inf), 'ymin': min(map(snd, P[d]), default=inf), 'ymax': max(map(snd, P[d]), default=-inf)} for d in dirs}
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
	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 < 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)


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))


import queue

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)


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)
ans = 10 ** 18
for t in s:
	area = (rpos(t) - lpos(t)) * (upos(t) - dpos(t))
	if area < ans:
		ans = area
print(ans)


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)
high = 10 ** 8
high = float(high)
low = 0.0
while high - low > 1e-06:
	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)))


def f_minimum_bounding_box(N, Positions, INF=float('inf')):
	(X, Y) = [{'L': [], 'R': [], 'U': [], 'D': []} for _ in range(2)]
	for (x, y, d) in Positions:
		X[d].append(int(x) * 2)
		Y[d].append(int(y) * 2)
	(xs, ys) = ([], [])
	for c in 'LRUD':
		if len(X[c]) != 0:
			xs.extend((max(X[c]), min(X[c])))
		if len(Y[c]) != 0:
			ys.extend((max(Y[c]), min(Y[c])))
	cand = []
	for x1 in xs:
		for x2 in xs:
			d = abs(x1 - x2)
			cand.extend((d, d // 2))
	for y1 in ys:
		for y2 in ys:
			d = abs(y1 - y2)
			cand.extend((d, d // 2))
	dx = {'L': -1, 'R': 1, 'U': 0, 'D': 0}
	dy = {'L': 0, 'R': 0, 'U': 1, 'D': -1}
	ans = INF
	for d in cand:
		(xmax, ymax, xmin, ymin) = (-INF, -INF, INF, INF)
		for c in 'LRUD':
			for i in range(len(X[c])):
				x = X[c][i] + dx[c] * d
				xmax = max(xmax, x)
				xmin = min(xmin, x)
			for j in range(len(Y[c])):
				y = Y[c][j] + dy[c] * d
				ymax = max(ymax, y)
				ymin = min(ymin, y)
		tmp = (xmax - xmin) * (ymax - ymin)
		ans = min(ans, tmp)
	return round(ans / 4, 12)
N = int(input())
Positions = [[i for i in input().split()] for j in range(N)]
print(f_minimum_bounding_box(N, Positions))


N = int(input())
inf = float('inf')
data = [[inf, -inf, inf, -inf] for i in range(4)]
dic = {'U': 0, 'D': 1, 'R': 2, 'L': 3}
for i in range(N):
	(x, y, d) = input().split()
	(x, y) = (int(x), int(y))
	u = data[dic[d]]
	u[0] = min(u[0], x)
	u[1] = max(u[1], x)
	u[2] = min(u[2], y)
	u[3] = max(u[3], y)
(a, b, c, d) = data[0]
(e, f, g, h) = data[1]
(i, j, k, l) = data[2]
(m, n, o, p) = data[3]
a = min(a, e)
b = max(b, f)
k = min(k, o)
l = max(l, p)
if a == inf:
	a = -inf
	b = inf
time = [0]
time.append(a - i)
time.append(m - a)
time.append((m - i) / 2)
time.append(b - j)
time.append(n - b)
time.append((n - j) / 2)
time.append(k - c)
time.append(g - k)
time.append((g - c) / 2)
time.append(l - d)
time.append(h - l)
time.append((h - d) / 2)
ans = inf
for t in time:
	if 0 <= t <= 10 ** 10:
		lst = []
		for u in data:
			lst.append(u[:])
		lst[2][0] += t
		lst[2][1] += t
		lst[0][2] += t
		lst[0][3] += t
		lst[3][0] -= t
		lst[3][1] -= t
		lst[1][2] -= t
		lst[1][3] -= t
		lsls = []
		for j in range(4):
			if j % 2 == 0:
				m = inf
				for i in range(4):
					m = min(m, lst[i][j])
				lsls.append(m)
			else:
				M = -inf
				for i in range(4):
					M = max(M, lst[i][j])
				lsls.append(M)
		ans = min(ans, (lsls[1] - lsls[0]) * (lsls[3] - lsls[2]))
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 > 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())
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 sys
sys.setrecursionlimit(2147483647)
INF = 10 ** 9
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

class D(object):

	def __init__(self):
		self.L = [INF] * 3
		self.R = [-INF] * 3

	def add(self, x, v):
		v += 1
		self.L[v] = min(self.L[v], x)
		self.R[v] = max(self.R[v], x)

	def get(self, t):
		l = INF
		r = -INF
		L = self.L
		R = self.R
		for i in range(3):
			l = min(L[i] + i * t, l)
			r = max(R[i] + i * t, r)
		return r - l

	def event(self):
		L = self.L
		R = self.R
		res = []
		for i in range(3):
			for j in range(i):
				t = (L[j] - L[i]) / (i - j)
				if t > 0:
					res.append(t)
		for i in range(3):
			for j in range(i):
				t = (R[j] - R[i]) / (i - j)
				if t > 0:
					res.append(t)
		return res

def resolve():
	n = int(input())
	xd = D()
	yd = D()
	for i in range(n):
		(x, y, d) = input().split()
		x = int(x)
		y = int(y)
		if d == 'R':
			xd.add(x, 1)
			yd.add(y, 0)
		elif d == 'L':
			xd.add(x, -1)
			yd.add(y, 0)
		elif d == 'U':
			xd.add(x, 0)
			yd.add(y, 1)
		elif d == 'D':
			xd.add(x, 0)
			yd.add(y, -1)
	T = [0] + xd.event() + yd.event()
	ans = float('inf')
	for t in T:
		ans = min(ans, xd.get(t) * yd.get(t))
	print(ans)
resolve()


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 x1.items():
		xmin = min(xmin, x + v * t)
	for (v, x) in x2.items():
		xmax = max(xmax, x + v * t)
	for (v, y) in y1.items():
		ymin = min(ymin, y + v * t)
	for (v, y) in 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)


def analyze(points, left_static, right_static):
	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])


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()


INF = float('inf')
from collections import defaultdict
N = int(input())
dx = defaultdict(list)
dy = defaultdict(list)
for i in range(N):
	(x, y, d) = input().split()
	x = int(x)
	y = int(y)
	dx[d].append(x)
	dy[d].append(y)
mxl = INF
if 'L' in dx:
	mxl = min(dx['L'])
mxr = INF
if 'R' in dx:
	mxr = min(dx['R'])
mxud = INF
if 'U' in dx:
	mxud = min(dx['U'])
if 'D' in dx:
	mxud = min(min(dx['D']), mxud)
Mxl = -INF
if 'L' in dx:
	Mxl = max(dx['L'])
Mxr = -INF
if 'R' in dx:
	Mxr = max(dx['R'])
Mxud = -INF
if 'U' in dx:
	Mxud = max(dx['U'])
if 'D' in dx:
	Mxud = max(max(dx['D']), Mxud)
myu = INF
if 'U' in dy:
	myu = min(dy['U'])
myd = INF
if 'D' in dy:
	myd = min(dy['D'])
mylr = INF
if 'L' in dy:
	mylr = min(dy['L'])
if 'R' in dy:
	mylr = min(min(dy['R']), mylr)
Myu = -INF
if 'U' in dy:
	Myu = max(dy['U'])
Myd = -INF
if 'D' in dy:
	Myd = max(dy['D'])
Mylr = -INF
if 'L' in dy:
	Mylr = max(dy['L'])
if 'R' in dy:
	Mylr = max(max(dy['R']), Mylr)

def xmin(t):
	return min(mxl - t, mxr + t, mxud)

def xmax(t):
	return max(Mxl - t, Mxr + t, Mxud)

def ymin(t):
	return min(myu + t, myd - t, mylr)

def ymax(t):
	return max(Myu + t, Myd - t, Mylr)
cand = [0, (mxl - mxr) / 2, mxl - mxud, mxud - mxr, (Mxl - Mxr) / 2, Mxl - Mxud, Mxud - Mxr, (myd - myu) / 2, mylr - myu, myd - mylr, (Myd - Myu) / 2, Mylr - Myu, Myd - Mylr]
ans = INF
for t in cand:
	if t < 0:
		continue
	ans = min(ans, (xmax(t) - xmin(t)) * (ymax(t) - ymin(t)))
print(ans)


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 sys
sys.setrecursionlimit(2147483647)
INF = 10 ** 9
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

def resolve():
	n = int(input())
	X = [[INF, -INF] for _ in range(3)]
	Y = [[INF, -INF] for _ in range(3)]
	for _ in range(n):
		(x, y, d) = input().split()
		x = int(x)
		y = int(y)
		if d == 'R':
			X[2][0] = min(X[2][0], x)
			X[2][1] = max(X[2][1], x)
			Y[1][0] = min(Y[1][0], y)
			Y[1][1] = max(Y[1][1], y)
		elif d == 'L':
			X[0][0] = min(X[0][0], x)
			X[0][1] = max(X[0][1], x)
			Y[1][0] = min(Y[1][0], y)
			Y[1][1] = max(Y[1][1], y)
		elif d == 'U':
			X[1][0] = min(X[1][0], x)
			X[1][1] = max(X[1][1], x)
			Y[2][0] = min(Y[2][0], y)
			Y[2][1] = max(Y[2][1], y)
		elif d == 'D':
			X[1][0] = min(X[1][0], x)
			X[1][1] = max(X[1][1], x)
			Y[0][0] = min(Y[0][0], y)
			Y[0][1] = max(Y[0][1], y)
	T = [0]
	for i in range(3):
		for j in range(i):
			t = -(X[i][0] - X[j][0]) / (i - j)
			if t > 0:
				T.append(t)
			t = -(X[i][1] - X[j][1]) / (i - j)
			if t > 0:
				T.append(t)
			t = -(Y[i][0] - Y[j][0]) / (i - j)
			if t > 0:
				T.append(t)
			t = -(Y[i][1] - Y[j][1]) / (i - j)
			if t > 0:
				T.append(t)

	def f(t):
		x_min = min(X[0][0], X[1][0] + t, X[2][0] + 2 * t)
		x_max = max(X[0][1], X[1][1] + t, X[2][1] + 2 * t)
		y_min = min(Y[0][0], Y[1][0] + t, Y[2][0] + 2 * t)
		y_max = max(Y[0][1], Y[1][1] + t, Y[2][1] + 2 * t)
		return (x_max - x_min) * (y_max - y_min)
	ans = float('inf')
	for t in T:
		ans = min(ans, f(t))
	print(ans)
resolve()


N = int(input())
INF = 10 ** 20
(max_Lx, max_Rx, max_UDx) = (-INF, -INF, -INF)
(min_Lx, min_Rx, min_UDx) = (INF, INF, INF)
(max_Uy, max_Dy, max_LRy) = (-INF, -INF, -INF)
(min_Uy, min_Dy, min_LRy) = (INF, INF, INF)
for _ in range(N):
	(x, y, d) = input().split()
	(x, y) = (int(x), int(y))
	if d == 'L':
		max_Lx = max(max_Lx, x)
		min_Lx = min(min_Lx, x)
		max_LRy = max(max_LRy, y)
		min_LRy = min(min_LRy, y)
	elif d == 'R':
		max_Rx = max(max_Rx, x)
		min_Rx = min(min_Rx, x)
		max_LRy = max(max_LRy, y)
		min_LRy = min(min_LRy, y)
	elif d == 'U':
		max_Uy = max(max_Uy, y)
		min_Uy = min(min_Uy, y)
		max_UDx = max(max_UDx, x)
		min_UDx = min(min_UDx, x)
	elif d == 'D':
		max_Dy = max(max_Dy, y)
		min_Dy = min(min_Dy, y)
		max_UDx = max(max_UDx, x)
		min_UDx = min(min_UDx, x)

def calc(t):
	max_x = max(max_Lx - t, max_UDx, max_Rx + t)
	min_x = min(min_Lx - t, min_UDx, min_Rx + t)
	max_y = max(max_Dy - t, max_LRy, max_Uy + t)
	min_y = min(min_Dy - t, min_LRy, min_Uy + t)
	return (max_x - min_x) * (max_y - min_y)
schedule = [0, max_UDx - max_Rx, max_Lx - max_UDx, (max_Lx - max_Rx) / 2, min_UDx - min_Rx, min_Lx - max_UDx, (min_Lx - min_Rx) / 2, max_LRy - max_Uy, max_Dy - max_LRy, (max_Dy - max_Uy) / 2, min_LRy - min_Uy, min_Dy - max_LRy, (min_Dy - min_Uy) / 2]
min_diff = INF
for t in schedule:
	if 0 <= t < INF / 10:
		min_diff = min(min_diff, calc(t))
print(min_diff)


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
input = sys.stdin.readline
n = int(input())
if n == 1:
	ans = 0
else:
	(u_list, d_list, r_list, l_list) = ([], [], [], [])
	(x_list, y_list) = ([], [])
	for i in range(n):
		(x, y, r) = [v for v in input().split()]
		(x, y) = (int(x), int(y))
		if r == 'U':
			u_list.append(y)
			x_list.append(x)
		elif r == 'D':
			d_list.append(y)
			x_list.append(x)
		elif r == 'R':
			r_list.append(x)
			y_list.append(y)
		elif r == 'L':
			l_list.append(x)
			y_list.append(y)
	x_list = sorted(x_list)
	y_list = sorted(y_list)
	u_list = sorted(u_list)
	d_list = sorted(d_list)
	r_list = sorted(r_list)
	l_list = sorted(l_list)
	if len(u_list) == n:
		ans = (x_list[-1] - x_list[0]) * (u_list[-1] - u_list[0])
	elif len(d_list) == n:
		ans = (x_list[-1] - x_list[0]) * (d_list[-1] - d_list[0])
	elif len(r_list) == n:
		ans = (y_list[-1] - y_list[0]) * (r_list[-1] - r_list[0])
	elif len(l_list) == n:
		ans = (y_list[-1] - y_list[0]) * (l_list[-1] - l_list[0])
	else:
		yp_list = []
		ym_list = []
		xp_list = []
		xm_list = []
		if y_list != []:
			yp_list.append((y_list[-1], 0))
			ym_list.append((y_list[0], 0))
		if u_list != []:
			yp_list.append((u_list[-1], 1))
			ym_list.append((u_list[0], 1))
		if d_list != []:
			yp_list.append((d_list[-1], -1))
			ym_list.append((d_list[0], -1))
		if x_list != []:
			xp_list.append((x_list[-1], 0))
			xm_list.append((x_list[0], 0))
		if r_list != []:
			xp_list.append((r_list[-1], 1))
			xm_list.append((r_list[0], 1))
		if l_list != []:
			xp_list.append((l_list[-1], -1))
			xm_list.append((l_list[0], -1))
		time_list = [0]

		def timemotome(inlist1, inlist2):
			ti = (inlist1[0] - inlist2[0]) / (inlist2[1] - inlist1[1])
			return ti

		def timemotome2(inlist):
			if len(inlist) == 2:
				t = timemotome(inlist[0], inlist[1])
				if t >= 0:
					time_list.append(t)
			elif len(inlist) == 3:
				t = timemotome(inlist[0], inlist[1])
				if t >= 0:
					time_list.append(t)
				t = timemotome(inlist[1], inlist[2])
				if t >= 0:
					time_list.append(t)
				t = timemotome(inlist[2], inlist[0])
				if t >= 0:
					time_list.append(t)
		timemotome2(xm_list)
		timemotome2(xp_list)
		timemotome2(yp_list)
		timemotome2(ym_list)

		def menseki(a):
			ymax = max([i[0] + i[1] * a for i in yp_list])
			ymin = min([i[0] + i[1] * a for i in ym_list])
			xmax = max([i[0] + i[1] * a for i in xp_list])
			xmin = min([i[0] + i[1] * a for i in xm_list])
			return (ymax - ymin) * (xmax - xmin)
		ans = 10 ** 17
		for i in list(set(time_list)):
			ans = min(menseki(i), ans)
print(ans)


from decimal import *
N = int(input())
nmove_x = [10 ** 9, -10 ** 9]
nmove_y = [10 ** 9, -10 ** 9]
move = {'U': [10 ** 9, -10 ** 9], 'D': [10 ** 9, -10 ** 9], 'R': [10 ** 9, -10 ** 9], 'L': [10 ** 9, -10 ** 9]}
for _ in range(N):
	(x, y, d) = map(str, input().split())
	(x, y) = [int(x), int(y)]
	if d in 'UD':
		move[d] = [min([move[d][0], y]), max([move[d][1], y])]
		nmove_x = [min([nmove_x[0], x]), max([nmove_x[1], x])]
	else:
		move[d] = [min([move[d][0], x]), max([move[d][1], x])]
		nmove_y = [min([nmove_y[0], y]), max([nmove_y[1], y])]

def get_bb(t):
	x_mx = max([move['R'][1] + t, move['L'][1] - t, nmove_x[1]])
	x_mn = min([move['R'][0] + t, move['L'][0] - t, nmove_x[0]])
	y_mx = max([move['U'][1] + t, move['D'][1] - t, nmove_y[1]])
	y_mn = min([move['U'][0] + t, move['D'][0] - t, nmove_y[0]])
	return (x_mx - x_mn) * (y_mx - y_mn)
(l, r) = [Decimal('0'), Decimal('10000000000')]
for _ in range(500):
	m = Decimal(l + r) / 2
	if get_bb(m - Decimal('0.00000001')) < get_bb(m + Decimal('0.00000001')):
		r = m
	else:
		l = m
print(get_bb(m))


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()


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 sys
n = int(input())
inf = float('inf')
xmin = [inf, inf, inf]
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)


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.0)
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.0)
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)


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):
	global mod
	return (x + y) % mod

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

def mod_inv(x):
	global 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 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)
main()


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]))


def timecalc(p1, p2, speed):
	(h1, h2) = p1
	(l1, l2) = p2
	return ((h1 - l1) / speed, (h1 - l2) / speed, (h2 - l1) / speed, (h2 - l2) / speed)
n = int(input())
ans = 2 ** 62
X = []
Y = []
U = []
D = []
L = []
R = []
for i in range(n):
	xin = input().split()
	(x, y, dir) = (int(xin[0]), int(xin[1]), xin[2])
	if dir == 'U':
		X.append(x)
		U.append(y)
	elif dir == 'D':
		X.append(x)
		D.append(y)
	elif dir == 'L':
		Y.append(y)
		L.append(x)
	else:
		Y.append(y)
		R.append(x)
if n == 1:
	print(0)
	exit(0)
if X:
	X = [max(X), min(X)]
if Y:
	Y = [max(Y), min(Y)]
if U:
	U = [max(U), min(U)]
if D:
	D = [max(D), min(D)]
if L:
	L = [max(L), min(L)]
if R:
	R = [max(R), min(R)]
T = []
if X and R:
	T.extend([i for i in timecalc(X, R, 1) if i > 0])
if L and X:
	T.extend([i for i in timecalc(L, X, 1) if i > 0])
if Y and U:
	T.extend([i for i in timecalc(Y, U, 1) if i > 0])
if D and Y:
	T.extend([i for i in timecalc(D, Y, 1) if i > 0])
if L and R:
	T.extend([i for i in timecalc(L, R, 2) if i > 0])
if D and U:
	T.extend([i for i in timecalc(D, U, 2) if i > 0])
T = list(set(T))
T.append(0)
for i in T:
	xmax = -10 ** 9
	ymax = -10 ** 9
	xmin = 10 ** 9
	ymin = 10 ** 9
	if X:
		xmax = max(xmax, X[0])
		xmin = min(xmin, X[1])
	if Y:
		ymax = max(ymax, Y[0])
		ymin = min(ymin, Y[1])
	if U:
		ymax = max(ymax, U[0] + i)
		ymin = min(ymin, U[1] + i)
	if D:
		ymax = max(ymax, D[0] - i)
		ymin = min(ymin, D[1] - i)
	if L:
		xmax = max(xmax, L[0] - i)
		xmin = min(xmin, L[1] - i)
	if R:
		xmax = max(xmax, R[0] + i)
		xmin = min(xmin, R[1] + i)
	ans = min(ans, (xmax - xmin) * (ymax - ymin))
print(ans)


n = int(input())
xy = [[], [], [], []]
s = {'L': 0, 'R': 1, 'U': 2, 'D': 3}
for i in range(n):
	(x, y, d) = input().split()
	xy[s[d]] += [[int(x), int(y)]]
q = -10 ** 9
p = [[q, q, q] for i in range(4)]
ss = [[0, 2, 1, 1], [1, 1, 2, 0]]
pm = [1, -1, 1, -1]
for i in range(4):
	if xy[i]:
		for j in range(4):
			ps = ss[j // 2][i]
			z = max(xy[i], key=lambda z: z[j // 2] * pm[j])
			p[j][ps] = max(p[j][ps], z[j // 2] * pm[j])
t = {0}
for i in range(4):
	z = [u * pm[i] for u in p[i]]
	t = t | {z[1] - z[2], z[0] - z[1], (z[0] - z[2]) / 2}

def dis(u, v):
	return max(p[0 + v][0] - u, p[0 + v][1], p[0 + v][2] + u) - min(-p[1 + v][0] - u, -p[1 + v][1], -p[1 + v][2] + u)
print(min([dis(u, 0) * dis(u, 2) for u in t if u <= 2 * 10 ** 8 and u >= 0]))


n = int(input())
info = [list(input().split()) for i in range(n)]
for i in range(n):
	(x, y, dire) = info[i]
	info[i] = (int(x), int(y), dire)
INF = 10 ** 18

def solve_x(mid, op=max, e=-INF):
	(x0, x1) = (e, e)
	for (x, _, dire) in info:
		if dire == 'U' or dire == 'D':
			(x0, x1) = (op(x, x0), op(x, x1))
		elif dire == 'R':
			(x0, x1) = (op(x + mid, x0), op(x + mid + 1, x1))
		else:
			(x0, x1) = (op(x - mid, x0), op(x - mid - 1, x1))
	return (x0, x1)

def solve_y(mid, op=max, e=-INF):
	(y0, y1) = (e, e)
	for (_, y, dire) in info:
		if dire == 'L' or dire == 'R':
			(y0, y1) = (op(y, y0), op(y, y1))
		elif dire == 'U':
			(y0, y1) = (op(y + mid, y0), op(y + mid + 1, y1))
		else:
			(y0, y1) = (op(y - mid, y0), op(y - mid - 1, y1))
	return (y0, y1)

def solve_s(t):
	x_max = -INF * INF
	x_min = INF * INF
	y_max = -INF * INF
	y_min = INF * INF
	for (x, y, dire) in info:
		if dire == 'L':
			x_max = max(x - t, x_max)
			x_min = min(x - t, x_min)
			y_max = max(y, y_max)
			y_min = min(y, y_min)
		if dire == 'R':
			x_max = max(x + t, x_max)
			x_min = min(x + t, x_min)
			y_max = max(y, y_max)
			y_min = min(y, y_min)
		if dire == 'D':
			x_max = max(x, x_max)
			x_min = min(x, x_min)
			y_max = max(y - t, y_max)
			y_min = min(y - t, y_min)
		if dire == 'U':
			x_max = max(x, x_max)
			x_min = min(x, x_min)
			y_max = max(y + t, y_max)
			y_min = min(y + t, y_min)
	return (x_max - x_min) * (y_max - y_min)
ts = set([])
ok = -1
ng = INF
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	(x0, x1) = solve_x(mid, op=max, e=-INF)
	if x0 > x1:
		ok = mid
	else:
		ng = mid
(ts.add(ok - 2), ts.add(ok - 1), ts.add(ok), ts.add(ng), ts.add(ng + 1), ts.add(ng + 2))
ok = -1
ng = INF
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	(x0, x1) = solve_x(mid, op=max, e=-INF)
	if x0 < x1:
		ng = mid
	else:
		ok = mid
(ts.add(ok - 2), ts.add(ok - 1), ts.add(ok), ts.add(ng), ts.add(ng + 1), ts.add(ng + 2))
ok = -1
ng = INF
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	(x0, x1) = solve_x(mid, op=min, e=INF)
	if x0 < x1:
		ok = mid
	else:
		ng = mid
(ts.add(ok - 2), ts.add(ok - 1), ts.add(ok), ts.add(ng), ts.add(ng + 1), ts.add(ng + 2))
ok = -1
ng = INF
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	(x0, x1) = solve_x(mid, op=min, e=INF)
	if x0 > x1:
		ng = mid
	else:
		ok = mid
(ts.add(ok - 2), ts.add(ok - 1), ts.add(ok), ts.add(ng), ts.add(ng + 1), ts.add(ng + 2))
ok = -1
ng = INF
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	(y0, y1) = solve_y(mid, op=max, e=-INF)
	if y0 > y1:
		ok = mid
	else:
		ng = mid
(ts.add(ok - 2), ts.add(ok - 1), ts.add(ok), ts.add(ng), ts.add(ng + 1), ts.add(ng + 2))
ok = -1
ng = INF
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	(y0, y1) = solve_y(mid, op=max, e=-INF)
	if y0 < y1:
		ng = mid
	else:
		ok = mid
(ts.add(ok - 2), ts.add(ok - 1), ts.add(ok), ts.add(ng), ts.add(ng + 1), ts.add(ng + 2))
ok = -1
ng = INF
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	(y0, y1) = solve_y(mid, op=min, e=INF)
	if y0 < y1:
		ok = mid
	else:
		ng = mid
(ts.add(ok - 2), ts.add(ok - 1), ts.add(ok), ts.add(ng), ts.add(ng + 1), ts.add(ng + 2))
ok = -1
ng = INF
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	(y0, y1) = solve_y(mid, op=min, e=INF)
	if y0 > y1:
		ng = mid
	else:
		ok = mid
(ts.add(ok - 2), ts.add(ok - 1), ts.add(ok), ts.add(ng), ts.add(ng + 1), ts.add(ng + 2))
ans = INF * INF
for t in ts:
	if t >= INF - 10:
		continue
	if t - 0.5 >= 0:
		ans = min(solve_s(t - 0.5), ans)
	if t >= 0:
		ans = min(solve_s(t), ans)
	if t + 0.5 >= 0:
		ans = min(solve_s(t + 0.5), ans)
print(ans)


import sys
from math import floor

def check(t):
	(maxx, minx, maxy, miny) = (ud_maxx, ud_minx, lr_maxy, lr_miny)
	for (x, y) in dots['R']:
		maxx = max(maxx, x + t)
		minx = min(minx, x + t)
	for (x, y) in dots['L']:
		maxx = max(maxx, x - t)
		minx = min(minx, x - t)
	for (x, y) in dots['U']:
		maxy = max(maxy, y + t)
		miny = min(miny, y + t)
	for (x, y) in dots['D']:
		maxy = max(maxy, y - t)
		miny = min(miny, y - t)
	return (maxx - minx) * (maxy - miny)
n = int(input())
dots = {'R': set(), 'L': set(), 'U': set(), 'D': set()}
(lr_maxy, lr_miny, ud_maxx, ud_minx) = (-1000000000.0, 1000000000.0, -1000000000.0, 1000000000.0)
for line in sys.stdin:
	(x, y, d) = line.rstrip().split()
	(x, y) = (int(x), int(y))
	dots[d].add((x, y))
	if d in 'LR':
		lr_maxy = max(lr_maxy, y)
		lr_miny = min(lr_miny, y)
	else:
		ud_maxx = max(ud_maxx, x)
		ud_minx = min(ud_minx, x)
l = 0.0
r = float(1 << 30)
while l < r - 1:
	m1 = l + floor((r - l) / 3 * 2) / 2
	m2 = l + floor((r - l) / 3 * 4) / 2
	c1 = check(m1)
	c2 = check(m2)
	if c1 >= c2:
		l = m1
	else:
		r = m2
ans = float(1e+17)
l = max(0.0, floor(l * 2 - 16) / 2)
while l <= r + 8:
	ans = min(ans, check(l))
	l += 0.5
print(ans)


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

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	x = [int()] * N
	y = [int()] * N
	d = [str()] * N
	for i in range(N):
		x[i] = int(next(tokens))
		y[i] = int(next(tokens))
		d[i] = next(tokens)
	solve(N, x, y, d)
main()


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 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)))


from scipy.optimize import fmin
N = int(input())
INF = 10 ** 18
fixed_x = [INF, -INF]
R = [INF, -INF]
L = [INF, -INF]
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)


INF = 10 ** 18

def calc(point_list, t):
	(x_min, y_min, x_max, y_max) = (INF, INF, -INF, -INF)
	for point in point_list:
		(x, y, d) = point
		dx = t if d == 'R' else -t if d == 'L' else 0
		dy = t if d == 'U' else -t if d == 'D' else 0
		x_min = min(x_min, x + dx)
		x_max = max(x_max, x + dx)
		y_min = min(y_min, y + dy)
		y_max = max(y_max, y + dy)
	return (x_max - x_min) * (y_max - y_min)

def main():
	N = int(input())
	point_list = list()
	(x_min, y_min, x_max, y_max) = (INF, INF, -INF, -INF)
	for _ in range(N):
		(X, Y, D) = input().split()
		X = int(X)
		x_min = min(x_min, X)
		x_max = max(x_max, X)
		Y = int(Y)
		y_min = min(y_min, Y)
		y_max = max(y_max, Y)
		point_list.append((X, Y, D))
	if N == 1:
		print(0)
		return
	(t_left, t_right) = (0, 2 * max(x_max - x_min, y_max - y_min))
	(v_left, v_right) = (calc(point_list, t_left), calc(point_list, t_right))
	while True:
		dt = t_right - t_left
		if dt < 10 ** (-8):
			break
		(t_in_left, t_in_right) = (t_left + dt / 3, t_right - dt / 3)
		(v_in_left, v_in_right) = (calc(point_list, t_in_left), calc(point_list, t_in_right))
		if v_in_left < v_in_right:
			t_right = t_in_right
			v_right = v_in_right
		else:
			t_left = t_in_left
			v_left = v_in_left
	print(v_left)
main()


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) = 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])
	inflections.add(max(0, left_max - const_x_max))
	inflections.add(max(0, (left_max - right_max) / 2))
	inflections.add(max(0, const_x_max - right_max))
	inflections.add(max(0, const_x_min - right_min))
	inflections.add(max(0, (left_min - right_min) / 2))
	inflections.add(max(0, left_min - const_x_min))
	inflections.add(max(0, down_max - const_y_max))
	inflections.add(max(0, (down_max - up_max) / 2))
	inflections.add(max(0, const_y_max - up_max))
	inflections.add(max(0, const_y_min - up_min))
	inflections.add(max(0, (down_min - up_min) / 2))
	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
print(main())


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return map(int, input().split())

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

def main():
	mod = 10 ** 9 + 7
	N = I()
	if N == 1:
		print(0)
		exit()
	inf = 10 ** 10
	X = [0] * N
	Y = [0] * N
	D = [0] * N
	for i in range(N):
		xyd = input().split()
		X[i] = int(xyd[0])
		Y[i] = int(xyd[1])
		D[i] = xyd[2]

	def calc_ts(S, XX):
		if S == 'X':
			L = 'L'
			R = 'R'
		else:
			L = 'D'
			R = 'U'
		xmin = [inf, inf, inf]
		xmax = [-inf, -inf, -inf]
		for i in range(N):
			x = XX[i]
			d = D[i]
			if d == L:
				xmin[0] = min(xmin[0], x)
				xmax[0] = max(xmax[0], x)
			elif d == R:
				xmin[2] = min(xmin[2], x)
				xmax[2] = max(xmax[2], x)
			else:
				xmin[1] = min(xmin[1], x)
				xmax[1] = max(xmax[1], x)
		ts = []
		t = xmin[0] - xmin[1]
		if t > 0:
			ts.append(t)
		t = xmin[0] - xmin[2]
		if t > 0:
			ts.append(t / 2)
		t = xmin[1] - xmin[2]
		if t > 0:
			ts.append(t)
		t = xmax[0] - xmax[1]
		if t > 0:
			ts.append(t)
		t = xmax[0] - xmax[2]
		if t > 0:
			ts.append(t / 2)
		t = xmax[1] - xmax[2]
		if t > 0:
			ts.append(t)
		return ts
	ts_all = [0]
	ts_all += calc_ts('X', X)
	ts_all += calc_ts('Y', Y)

	def calc(t):
		xmin = inf
		xmax = -inf
		ymin = inf
		ymax = -inf
		for i in range(N):
			x = X[i]
			y = Y[i]
			d = D[i]
			if d == 'L':
				xmin = min(xmin, x - t)
				xmax = max(xmax, x - t)
				ymin = min(ymin, y)
				ymax = max(ymax, y)
			elif d == 'R':
				xmin = min(xmin, x + t)
				xmax = max(xmax, x + t)
				ymin = min(ymin, y)
				ymax = max(ymax, y)
			elif d == 'U':
				xmin = min(xmin, x)
				xmax = max(xmax, x)
				ymin = min(ymin, y + t)
				ymax = max(ymax, y + t)
			else:
				xmin = min(xmin, x)
				xmax = max(xmax, x)
				ymin = min(ymin, y - t)
				ymax = max(ymax, y - t)
		return (xmax - xmin) * (ymax - ymin)
	ans = inf ** 2
	for t in ts_all:
		temp = calc(t)
		ans = min(ans, temp)
	print(ans)
main()


n = int(input())
m = {}
for _ in range(n):
	(x, y, d) = input().split()
	(x, y) = (int(x) * 2, int(y) * 2)
	if d not in m:
		m[d] = [1000000000, -1000000000, 1000000000, -1000000000]
	m[d][0] = min(m[d][0], x)
	m[d][1] = max(m[d][1], x)
	m[d][2] = min(m[d][2], y)
	m[d][3] = max(m[d][3], y)
dx = {'L': -1, 'R': 1, 'U': 0, 'D': 0}
dy = {'L': 0, 'R': 0, 'U': 1, 'D': -1}
px = []
py = []
for d in 'LRUD':
	if d in m:
		px.append((m[d][0], dx[d]))
		px.append((m[d][1], dx[d]))
		py.append((m[d][2], dy[d]))
		py.append((m[d][3], dy[d]))
times = [0]

def append(pa, pb):
	(a, da) = pa
	(b, db) = pb
	if db != da:
		t = (a - b) // (db - da)
		if t >= 0:
			times.append(t)
for i in range(len(px)):
	for j in range(i + 1, len(px)):
		append(px[i], px[j])
for i in range(len(py)):
	for j in range(i + 1, len(py)):
		append(py[i], py[j])
ret = 1000000000000000000
for t in times:
	bb = [1000000000, -1000000000, 1000000000, -1000000000]
	for d in 'LRUD':
		if d in m:
			bb[0] = min(bb[0], m[d][0] + dx[d] * t)
			bb[1] = max(bb[1], m[d][1] + dx[d] * t)
			bb[2] = min(bb[2], m[d][2] + dy[d] * t)
			bb[3] = max(bb[3], m[d][3] + dy[d] * t)
	ret = min(ret, (bb[1] - bb[0]) * (bb[3] - bb[2]))
print(ret / 4.0)


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))
xdic = defaultdict(set)
for (x, d) in xlist:
	xdic[d].add(x)
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)
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))

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
			elif 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)
cand_t = [0] + list(cand_time_x) + list(cand_time_y)

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))
	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)


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

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) = (-1000000000.0, 1000000000.0, -1000000000.0, 1000000000.0)
(l_maxx, l_minx, r_maxx, r_minx) = (-1000000000.0, 1000000000.0, -1000000000.0, 1000000000.0)
(u_maxy, u_miny, d_maxy, d_miny) = (-1000000000.0, 1000000000.0, -1000000000.0, 1000000000.0)
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)


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-09, 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))


def f_minimum_bounding_box(N, Positions, INF=float('inf')):
	(x_dict, y_dict) = [{'L': [], 'R': [], 'U': [], 'D': []} for _ in range(2)]
	for (x, y, d) in Positions:
		x_dict[d].append(int(x) * 2)
		y_dict[d].append(int(y) * 2)
	(xs, ys) = ([], [])
	for c in 'LRUD':
		if len(x_dict[c]) != 0:
			xs.extend((max(x_dict[c]), min(x_dict[c])))
		if len(y_dict[c]) != 0:
			ys.extend((max(y_dict[c]), min(y_dict[c])))

	def f(lst, ret=[]):
		for e1 in lst:
			for e2 in lst:
				d = abs(e1 - e2)
				ret.extend((d, d // 2))
		return ret
	time_candidates = f(xs) + f(ys)
	dx = {'L': -1, 'R': 1, 'U': 0, 'D': 0}
	dy = {'L': 0, 'R': 0, 'U': 1, 'D': -1}
	ans = INF
	for d in time_candidates:
		(xmax, ymax, xmin, ymin) = (-INF, -INF, INF, INF)
		for c in 'LRUD':
			for i in x_dict[c]:
				x = i + dx[c] * d
				(xmax, xmin) = (max(xmax, x), min(xmin, x))
			for j in y_dict[c]:
				y = j + dy[c] * d
				(ymax, ymin) = (max(ymax, y), min(ymin, y))
		ans = min(ans, (xmax - xmin) * (ymax - ymin) / 4)
	return round(ans, 12)
N = int(input())
Positions = [[i for i in input().split()] for j in range(N)]
print(f_minimum_bounding_box(N, Positions))


def examA():
	import numpy as np

	def powDetMod(n, arr, k, MOD=-1):
		repeat = 60
		local_doubling = [[] for _ in range(repeat + 1)]
		local_doubling[0] = arr
		for i in range(repeat):
			local_doubling[i + 1] = np.dot(local_doubling[i], local_doubling[i])
			if MOD > 0:
				for h in range(n):
					for w in range(n):
						local_doubling[i + 1][h][w] %= MOD
		now = [[1 if i == j else 0 for i in range(n)] for j in range(n)]
		for i in range(repeat + 1):
			if k & 1 << i > 0:
				now = np.dot(now, local_doubling[i])
				if MOD > 0:
					for h in range(n):
						for w in range(n):
							now[h][w] %= MOD
		return now
	(L, A, B, M) = LI()
	C = [0] * 18
	cnt = L
	for i in range(18):
		if pow(10, i + 1) - 1 - A < 0:
			continue
		C[i] = 1 + (pow(10, i + 1) - 1 - A) // B
		if pow(10, i) - 1 - A >= 0:
			C[i] -= 1 + (pow(10, i) - 1 - A) // B
		if C[i] >= cnt:
			C[i] = cnt
			break
		cnt -= C[i]
	X = np.array([0, A, B])
	for i in range(18):
		now = [[pow(10, i + 1, M), 0, 0], [1, 1, 0], [0, 1, 1]]
		now = np.array(now)
		arr = powDetMod(3, now, C[i], M)
		X = np.dot(X, arr) % M
	ans = X[0] % M
	print(ans)
	return

def examB():
	N = I()
	R = [inf, -inf]
	L = [inf, -inf]
	U = [inf, -inf]
	D = [inf, -inf]
	X = [inf, -inf]
	Y = [inf, -inf]
	for _ in range(N):
		(x, y, s) = LSI()
		(x, y) = (int(x), int(y))
		if s == 'R':
			if x < R[0]:
				R[0] = x
			if x > R[1]:
				R[1] = x
			if y < Y[0]:
				Y[0] = y
			if y > Y[1]:
				Y[1] = y
		elif s == 'L':
			if x < L[0]:
				L[0] = x
			if x > L[1]:
				L[1] = x
			if y < Y[0]:
				Y[0] = y
			if y > Y[1]:
				Y[1] = y
		elif s == 'U':
			if y < U[0]:
				U[0] = y
			if y > U[1]:
				U[1] = y
			if x < X[0]:
				X[0] = x
			if x > X[1]:
				X[1] = x
		elif s == 'D':
			if y < D[0]:
				D[0] = y
			if y > D[1]:
				D[1] = y
			if x < X[0]:
				X[0] = x
			if x > X[1]:
				X[1] = x

	def calc_area(t):
		x = max(R[1] + t, L[1] - t, X[1]) - min(R[0] + t, L[0] - t, X[0])
		y = max(U[1] + t, D[1] - t, Y[1]) - min(U[0] + t, D[0] - t, Y[0])
		if x <= 0 or y <= 0:
			return 0
		return x * y
	ans = calc_area(0)
	for i in [0, 1]:
		for j in [0, 1]:
			if R[i] <= X[j]:
				T = X[j] - R[i]
				ans = min(ans, calc_area(T))
			if L[i] >= X[j]:
				T = L[i] - X[j]
				ans = min(ans, calc_area(T))
			if R[i] <= L[j]:
				T = dec((L[j] - R[i]) / 2)
				ans = min(ans, calc_area(T))
			if U[i] <= Y[j]:
				T = Y[j] - U[i]
				ans = min(ans, calc_area(T))
			if D[i] >= Y[j]:
				T = D[i] - Y[j]
				ans = min(ans, calc_area(T))
			if U[i] <= D[j]:
				T = dec((D[j] - U[i]) / 2)
				ans = min(ans, calc_area(T))
	print(ans)
	return
from decimal import Decimal as dec
import sys, bisect, itertools, heapq, math, random
from copy import deepcopy
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def I():
	return int(input())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def DI():
	return dec(input())

def LDI():
	return list(map(dec, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = 10 ** (-12)
alphabet = [chr(ord('a') + i) for i in range(26)]
sys.setrecursionlimit(10 ** 7)
examB()


N = int(input())
points = []
ds = []
for i in range(N):
	(x, y, d) = input().split()
	(x, y) = map(int, (x, y))
	if d == 'L':
		d = (-1, 0)
	if d == 'R':
		d = (1, 0)
	if d == 'U':
		d = (0, 1)
	if d == 'D':
		d = (0, -1)
	points.append((x, y))
	ds.append(d)
if N == 1:
	print(0)
	exit()
(x, y) = list(zip(*points))
(xmax, xmin, ymax, ymin) = (max(x), min(x), max(y), min(y))

def region(p):
	(x, y) = list(zip(*p))
	return (max(x) - min(x)) * (max(y) - min(y))

def process(p, d, second=1):
	return [(p[i][0] + second * d[i][0], p[i][1] + second * d[i][1]) for i in range(N)]

def func(x):
	return region(process(points, ds, x))

def ternary_search(f, x_min, x_max, epsilon=1e-15):
	while True:
		(x1, x2) = (1 / 3 * (x_max - x_min) + x_min, 2 / 3 * (x_max - x_min) + x_min)
		gap = f(x1) - f(x2)
		if gap < 0:
			x_max = x2
		else:
			x_min = x1
		if abs(gap) <= epsilon:
			break
	return (x_max + x_min) / 2
t_max = 4 * max(xmax - xmin, ymax - ymin)
t_min = 0
x_opt = ternary_search(func, t_min, t_max, epsilon=1e-15)
print(func(x_opt))


import sys
N = int(input())
(LU, LD, LR, LL) = ([], [], [], [])
for _ in range(N):
	(x, y, d) = sys.stdin.readline().split()
	x = int(x)
	y = int(y)
	if d == 'R':
		LR.append((x, y))
	elif d == 'L':
		LL.append((x, y))
	elif d == 'U':
		LU.append((x, y))
	elif d == 'D':
		LD.append((x, y))
if LR:
	(lrx, lry) = map(list, zip(*LR))
else:
	(lrx, lry) = ([], [])
if LL:
	(llx, lly) = map(list, zip(*LL))
else:
	(llx, lly) = ([], [])
if LU:
	(lux, luy) = map(list, zip(*LU))
else:
	(lux, luy) = ([], [])
if LD:
	(ldx, ldy) = map(list, zip(*LD))
else:
	(ldx, ldy) = ([], [])
inf = 100000000000000.0
maxxp = max(lrx + [-inf])
maxxz = max(lux + ldx + [-inf])
maxxm = max(llx + [-inf])
minxp = min(lrx + [inf])
minxz = min(lux + ldx + [inf])
minxm = min(llx + [inf])
maxyp = max(luy + [-inf])
maxyz = max(lly + lry + [-inf])
maxym = max(ldy + [-inf])
minyp = min(luy + [inf])
minyz = min(lly + lry + [inf])
minym = min(ldy + [inf])

def calc(t):
	maxx = max(maxxp + t, maxxz, maxxm - t)
	minx = min(minxp + t, minxz, minxm - t)
	maxy = max(maxyp + t, maxyz, maxym - t)
	miny = min(minyp + t, minyz, minym - t)
	return abs(maxx - minx) * abs(maxy - miny)
lo = 0.0
hi = 10000000000.0
for _ in range(1000):
	b1 = (2 * lo + hi) / 3
	b2 = (lo + 2 * hi) / 3
	if calc(b1) < calc(b2):
		hi = b2
	else:
		lo = b1
print(calc(lo))


import sys, heapq
from collections import deque, defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
DBG = True and False

def ddprint(x):
	if DBG:
		print(x)
BIG = 10 ** 18
n = inn()
rx = []
udx = []
lx = []
uy = []
rly = []
dy = []
for i in range(n):
	(x, y, d) = input().split()
	x = int(x)
	y = int(y)
	if d == 'R':
		rx.append(x)
		rly.append(y)
	elif d == 'L':
		lx.append(x)
		rly.append(y)
	elif d == 'U':
		udx.append(x)
		uy.append(y)
	elif d == 'D':
		udx.append(x)
		dy.append(y)
nor = len(rx) == 0
nol = len(lx) == 0
nou = len(uy) == 0
nod = len(dy) == 0
noud = nou and nod
norl = nor and nol
if not nor:
	rx.sort()
	rmax = rx[-1]
	rmin = rx[0]
if not nol:
	lx.sort()
	lmax = lx[-1]
	lmin = lx[0]
if not nou:
	uy.sort()
	umax = uy[-1]
	umin = uy[0]
if not nod:
	dy.sort()
	dmax = dy[-1]
	dmin = dy[0]
if not noud:
	udx.sort()
	udmax = udx[-1]
	udmin = udx[0]
if not norl:
	rly.sort()
	rlmax = rly[-1]
	rlmin = rly[0]
ddprint(rx)
ddprint(udx)
ddprint(lx)

def foo(t):
	ddprint('foo t: {}'.format(t))
	xmax = -BIG
	if not nor:
		xmax = max(xmax, rmax + t)
	if not noud:
		xmax = max(xmax, udmax)
	if not nol:
		xmax = max(xmax, lmax - t)
	xmin = BIG
	if not nor:
		xmin = min(xmin, rmin + t)
	if not noud:
		xmin = min(xmin, udmin)
	if not nol:
		xmin = min(xmin, lmin - t)
	ymax = -BIG
	if not nou:
		ymax = max(ymax, umax + t)
	if not norl:
		ymax = max(ymax, rlmax)
	if not nod:
		ymax = max(ymax, dmax - t)
	ymin = BIG
	if not nou:
		ymin = min(ymin, umin + t)
	if not norl:
		ymin = min(ymin, rlmin)
	if not nod:
		ymin = min(ymin, dmin - t)
	z = abs((xmax - xmin) * (ymax - ymin))
	ddprint('xmax {} xmin {} ymax {} ymin {} rtn {}'.format(xmax, xmin, ymax, ymin, z))
	return z
ts = [0]
if not noud:
	if not nor:
		ts.append(max(0, udmax - rmax))
		ts.append(max(0, udmin - rmin))
	if not nol:
		ts.append(max(0, lmax - udmax))
		ts.append(max(0, lmin - udmin))
if not nol and (not nor):
	ts.append(max(0, (lmax - rmax) / 2))
	ts.append(max(0, (lmin - rmin) / 2))
if not norl:
	if not nou:
		ts.append(max(0, rlmax - umax))
		ts.append(max(0, rlmin - umin))
	if not nod:
		ts.append(max(0, dmax - rlmax))
		ts.append(max(0, dmin - rlmin))
if not nod and (not nou):
	ts.append(max(0, (dmax - umax) / 2))
	ts.append(max(0, (dmin - umin) / 2))
ts = list(set(ts))
mn = BIG
for t in ts:
	mn = min(mn, foo(t))
print(mn)


n = int(input())
xy = [[], [], [], []]
s = {'L': 0, 'R': 1, 'U': 2, 'D': 3}
for i in range(n):
	(x, y, d) = input().split()
	xy[s[d]] += [[int(x), int(y)]]
q = 10 ** 9
(xmax, xmin, ymax, ymin) = ([-q, -q, -q], [q, q, q], [-q, -q, -q], [q, q, q])
sx = [0, 2, 1, 1]
sy = [1, 1, 2, 0]
for i in range(4):
	if xy[i]:
		z = max(xy[i], key=lambda z: z[0])
		xmax[sx[i]] = max(xmax[sx[i]], z[0])
		z = min(xy[i], key=lambda z: z[0])
		xmin[sx[i]] = min(xmin[sx[i]], z[0])
		z = max(xy[i], key=lambda z: z[1])
		ymax[sy[i]] = max(ymax[sy[i]], z[1])
		z = min(xy[i], key=lambda z: z[1])
		ymin[sy[i]] = min(ymin[sy[i]], z[1])
t = set([0])
for z in [xmax, ymax]:
	if max(z) == z[1]:
		t.add(z[1] - z[2])
	elif max(z) == z[0]:
		if z[0] - z[1] < z[1] - z[2]:
			t.add(z[0] - z[1])
			t.add(z[1] - z[2])
		else:
			t.add((z[0] - z[2]) / 2)
for z in [xmin, ymin]:
	if min(z) == z[1]:
		t.add(z[0] - z[1])
	elif min(z) == z[2]:
		if z[1] - z[2] < z[0] - z[1]:
			t.add(z[1] - z[2])
			t.add(z[0] - z[1])
		else:
			t.add((z[0] - z[2]) / 2)
ans = 4 * 10 ** 16
for u in t:
	if u >= 2 * 10 ** 8:
		continue
	dx = max(xmax[0] - u, xmax[1], xmax[2] + u) - min(xmin[0] - u, xmin[1], xmin[2] + u)
	dy = max(ymax[0] - u, ymax[1], ymax[2] + u) - min(ymin[0] - u, ymin[1], ymin[2] + u)
	ans = min(ans, dx * dy)
print(ans)


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)


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))


import sys
input = sys.stdin.readline
N = int(input())
P = [input().split() for i in range(N)]
for i in range(N):
	P[i][0] = int(P[i][0])
	P[i][1] = int(P[i][1])

def ans(Q):
	MINX = 10 ** 15
	MAXX = -10 ** 15
	MINY = 10 ** 15
	MAXY = -10 ** 15
	for (x, y) in Q:
		MINX = min(MINX, x)
		MINY = min(MINY, y)
		MAXX = max(MAXX, x)
		MAXY = max(MAXY, y)
	return (MAXX - MINX) * (MAXY - MINY)

def time(t):
	Q = []
	for (x, y, s) in P:
		if s == 'R':
			x += t
		elif s == 'L':
			x -= t
		elif s == 'U':
			y += t
		else:
			y -= t
		Q.append([x, y])
	return Q
MIN = 0
MAX = 10 ** 10
while MAX - MIN >= 1:
	x = (MIN + MAX) // 2
	if ans(time(x)) > ans(time(x + 1 / 2)):
		MIN = x + 1 / 2
	else:
		MAX = x
print(min(ans(time(MAX)), ans(time(MIN))))


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)))


import sys

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 30
n = int(input())
p = [input().split() for _ in range(n)]
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)
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)
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 sys
input = sys.stdin.readline
from itertools import product
n = int(input())
(Rx, Ry, Lx, Ly, Ux, Uy, Dx, Dy) = ([], [], [], [], [], [], [], [])
for _ in range(n):
	(x, y, d) = input().split()
	x = int(x)
	y = int(y)
	if d == 'R':
		Rx.append(x)
		Ry.append(y)
	elif d == 'L':
		Lx.append(x)
		Ly.append(y)
	elif d == 'U':
		Ux.append(x)
		Uy.append(y)
	else:
		Dx.append(x)
		Dy.append(y)
inf = float('inf')
stay_x = [min(Ux + Dx + [inf]), max(Ux + Dx + [-inf])]
plus_x = [min(Rx + [inf]), max(Rx + [-inf])]
minus_x = [min(Lx + [inf]), max(Lx + [-inf])]
plus_y = [min(Uy + [inf]), max(Uy + [-inf])]
minus_y = [min(Dy + [inf]), max(Dy + [-inf])]
stay_y = [min(Ly + Ry + [inf]), max(Ly + Ry + [-inf])]
T = [0]
for (x1, x2) in product(minus_x, plus_x):
	if x1 in (-inf, inf) or x2 in (-inf, inf):
		continue
	t = (x1 - x2) / 2
	if t > 0:
		T.append(t)
for (x1, x2) in product(minus_x, stay_x):
	if x1 in (-inf, inf) or x2 in (-inf, inf):
		continue
	t = x1 - x2
	if t > 0:
		T.append(t)
for (x1, x2) in product(plus_x, stay_x):
	if x1 in (-inf, inf) or x2 in (-inf, inf):
		continue
	t = x2 - x1
	if t > 0:
		T.append(t)
for (y1, y2) in product(minus_y, plus_y):
	if y1 in (-inf, inf) or y2 in (-inf, inf):
		continue
	t = (y1 - y2) / 2
	if t > 0:
		T.append(t)
for (y1, y2) in product(minus_y, stay_y):
	if y1 in (-inf, inf) or y2 in (-inf, inf):
		continue
	t = y1 - y2
	if t > 0:
		T.append(t)
for (y1, y2) in product(plus_y, stay_y):
	if y1 in (-inf, inf) or y2 in (-inf, inf):
		continue
	t = y2 - y1
	if t > 0:
		T.append(t)
T = sorted(set(T))
T.append(10 ** 10)

def width(t):
	left = min(stay_x[0], plus_x[0] + t, minus_x[0] - t)
	right = max(stay_x[1], plus_x[1] + t, minus_x[1] - t)
	return right - left

def height(t):
	down = min(stay_y[0], plus_y[0] + t, minus_y[0] - t)
	up = max(stay_y[1], plus_y[1] + t, minus_y[1] - t)
	return up - down

def minS(x1, x2, y1, y2):
	(ax, bx) = (x2 - x1, x1)
	(ay, by) = (y2 - y1, y1)
	(a, b, c) = (ax * ay, ax * by + bx * ay, bx * by)
	if a <= 0:
		return min(x1 * y1, x2 * y2)
	m = -b / (2 * a)
	if m < 0 or m > 1:
		return min(x1 * y1, x2 * y2)
	return a * m ** 2 + b * m + c
l = len(T)
X = [width(t) for t in T]
Y = [height(t) for t in T]
ans = inf
for i in range(l - 1):
	(x1, x2) = (X[i], X[i + 1])
	(y1, y2) = (Y[i], Y[i + 1])
	ans = min(ans, minS(x1, x2, y1, y2))
print(ans)


n = int(input())
static_min_x = 10 ** 8
static_max_x = -10 ** 8
static_min_y = 10 ** 8
static_max_y = -10 ** 8
rx_max = -10 ** 8
rx_min = 10 ** 8
lx_max = -18 ** 8
lx_min = 10 ** 8
uy_max = -10 ** 8
uy_min = 10 ** 8
dy_max = -18 ** 8
dy_min = 10 ** 8
for _ in range(n):
	(x, y, d) = input().split()
	x = int(x)
	y = int(y)
	if d == 'R':
		rx_max = max(rx_max, x)
		rx_min = min(rx_min, x)
		static_max_y = max(static_max_y, y)
		static_min_y = min(static_min_y, y)
	elif d == 'L':
		lx_max = max(lx_max, x)
		lx_min = min(lx_min, x)
		static_max_y = max(static_max_y, y)
		static_min_y = min(static_min_y, y)
	elif d == 'U':
		uy_max = max(uy_max, y)
		uy_min = min(uy_min, y)
		static_max_x = max(static_max_x, x)
		static_min_x = min(static_min_x, x)
	else:
		dy_max = max(dy_max, y)
		dy_min = min(dy_min, y)
		static_max_x = max(static_max_x, x)
		static_min_x = min(static_min_x, x)

def calc_ans(t):
	max_x = max(rx_max + t, lx_max - t, static_max_x)
	min_x = min(rx_min + t, lx_min - t, static_min_x)
	max_y = max(uy_max + t, dy_max - t, static_max_y)
	min_y = min(uy_min + t, dy_min - t, static_min_y)
	return (max_x - min_x) * (max_y - min_y)
ans = calc_ans(0)
ans = min(ans, calc_ans(abs(rx_max - lx_max) / 2.0))
if lx_max > static_max_x:
	ans = min(ans, calc_ans(lx_max - static_max_x))
if static_max_x > rx_max:
	ans = min(ans, calc_ans(static_max_x - rx_max))
ans = min(ans, calc_ans(abs(rx_min - lx_min) / 2.0))
if lx_min > static_min_x:
	ans = min(ans, calc_ans(lx_min - static_min_x))
if static_min_x > rx_min:
	ans = min(ans, calc_ans(static_min_x - rx_min))
ans = min(ans, calc_ans(abs(uy_max - dy_max) / 2.0))
if dy_max > static_max_y:
	ans = min(ans, calc_ans(dy_max - static_max_y))
if static_max_y > uy_max:
	ans = min(ans, calc_ans(static_max_y - uy_max))
ans = min(ans, calc_ans(abs(uy_min - dy_min) / 2.0))
if dy_min > static_min_y:
	ans = min(ans, calc_ans(dy_min - static_min_y))
if static_min_y > uy_min:
	ans = min(ans, calc_ans(static_min_y - uy_min))
print(ans)


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)


N = int(input())
table = []
for i in range(N):
	(x, y, d) = input().split()
	(x, y) = (int(x), int(y))
	table.append((x, y, d))
anspos = [0]
inf = 10 ** 10
a = -inf
b = -inf
c = -inf
for i in range(N):
	(x, y, d) = table[i]
	if d == 'L':
		a = max(x, a)
	elif d == 'R':
		b = max(x, b)
	else:
		c = max(x, c)
anspos += [abs(a - b) / 2, abs(a - c), abs(b - c)]
a = inf
b = inf
c = inf
for i in range(N):
	(x, y, d) = table[i]
	if d == 'L':
		a = min(x, a)
	elif d == 'R':
		b = min(x, b)
	else:
		c = min(x, c)
anspos += [abs(a - b) / 2, abs(a - c), abs(b - c)]
a = -inf
b = -inf
c = -inf
for i in range(N):
	(x, y, d) = table[i]
	if d == 'U':
		a = max(y, a)
	elif d == 'D':
		b = max(y, b)
	else:
		c = max(y, c)
anspos += [abs(a - b) / 2, abs(a - c), abs(b - c)]
a = inf
b = inf
c = inf
for i in range(N):
	(x, y, d) = table[i]
	if d == 'D':
		a = min(y, a)
	elif d == 'U':
		b = min(y, b)
	else:
		c = min(y, c)
ans = 10 ** 30
anspos += [abs(a - b) / 2, abs(a - c), abs(b - c)]
for t in anspos:
	xmax = -inf
	xmin = inf
	ymax = -inf
	ymin = inf
	for i in range(N):
		(x, y, d) = table[i]
		if d == 'U':
			y += t
		elif d == 'D':
			y -= t
		elif d == 'L':
			x -= t
		elif d == 'R':
			x += t
		xmax = max(xmax, x)
		xmin = min(xmin, x)
		ymax = max(ymax, y)
		ymin = min(ymin, y)
	kai = (xmax - xmin) * (ymax - ymin)
	ans = min(ans, kai)
print(ans)


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])]
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):
	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):
	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):
	(p, q, r, s) = (x2 - x1, x1, y2 - y1, y1)
	(a, b, c) = (p * r, p * s + q * r, q * s)
	if a <= 0:
		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)


import sys
from itertools import combinations
input = sys.stdin.readline
n = int(input())
xl = []
xr = []
xc = []
yt = []
yb = []
yc = []
for i in range(n):
	(x, y, d) = input().split()
	(x, y) = (int(x), int(y))
	if d == 'R':
		xr.append(x)
		yc.append(y)
	elif d == 'L':
		xl.append(x)
		yc.append(y)
	elif d == 'U':
		xc.append(x)
		yt.append(y)
	else:
		xc.append(x)
		yb.append(y)
xr.sort()
xl.sort()
xc.sort()
yt.sort()
yb.sort()
yc.sort()
xr_min = xr[0] if xr else None
xl_min = xl[0] if xl else None
xc_min = xc[0] if xc else None
xmin = [xr_min, xl_min, xc_min]
xr_max = xr[-1] if xr else None
xl_max = xl[-1] if xl else None
xc_max = xc[-1] if xc else None
xmax = [xr_max, xl_max, xc_max]
yt_max = yt[-1] if yt else None
yb_max = yb[-1] if yb else None
yc_max = yc[-1] if yc else None
ymax = [yt_max, yb_max, yc_max]
yt_min = yt[0] if yt else None
yb_min = yb[0] if yb else None
yc_min = yc[0] if yc else None
ymin = [yt_min, yb_min, yc_min]

def cross(p1, p2):
	ret = []
	if p1 is None or p2 is None:
		return ret
	sub = abs(p1 - p2)
	ret.append(sub)
	ret.append(sub / 2)
	ret.append(sub / 2 + 1)
	return ret

def check(t, xmax, xmin, ymax, ymin):
	op = [+1, -1, 0]
	xmax_ = -float('inf')
	xmin_ = float('inf')
	ymax_ = -float('inf')
	ymin_ = float('inf')
	for (i, x) in enumerate(xmax):
		if x is not None:
			xmax_ = max(xmax_, x + t * op[i])
	for (i, x) in enumerate(xmin):
		if x is not None:
			xmin_ = min(xmin_, x + t * op[i])
	for (i, y) in enumerate(ymax):
		if y is not None:
			ymax_ = max(ymax_, y + t * op[i])
	for (i, y) in enumerate(ymin):
		if y is not None:
			ymin_ = min(ymin_, y + t * op[i])
	return (xmax_ - xmin_) * (ymax_ - ymin_)
time_candidate = [0]
for lis in [xmin, xmax, ymin, ymax]:
	for (p1, p2) in combinations(lis, 2):
		time_candidate.extend(cross(p1, p2))
ans = float('inf')
for i in set(time_candidate):
	ans_tmp = check(i, xmax, xmin, ymax, ymin)
	ans = min(ans, check(i, xmax, xmin, ymax, ymin))
print(ans)


n = int(input())
out_of_range = 1000000000
r = [out_of_range + 1, -out_of_range - 1]
l = [out_of_range + 1, -out_of_range - 1]
u = [out_of_range + 1, -out_of_range - 1]
d = [out_of_range + 1, -out_of_range - 1]
x_fixed = [out_of_range + 1, -out_of_range - 1]
y_fixed = [out_of_range + 1, -out_of_range - 1]
for _ in range(n):
	(x, y, di) = input().split()
	(x, y) = (int(x), int(y))
	if di == 'R':
		(r[0], r[1]) = (min(x, r[0]), max(x, r[1]))
		y_fixed[0] = min(y_fixed[0], y)
		y_fixed[1] = max(y_fixed[1], y)
	elif di == 'L':
		(l[0], l[1]) = (min(x, l[0]), max(x, l[1]))
		y_fixed[0] = min(y_fixed[0], y)
		y_fixed[1] = max(y_fixed[1], y)
	elif di == 'U':
		(u[0], u[1]) = (min(y, u[0]), max(y, u[1]))
		x_fixed[0] = min(x_fixed[0], x)
		x_fixed[1] = max(x_fixed[1], x)
	else:
		(d[0], d[1]) = (min(y, d[0]), max(y, d[1]))
		x_fixed[0] = min(x_fixed[0], x)
		x_fixed[1] = max(x_fixed[1], x)
exists_l = l[0] <= out_of_range
exists_r = r[0] <= out_of_range
exists_u = u[0] <= out_of_range
exists_d = d[0] <= out_of_range
exists_x_fixed = x_fixed[0] <= out_of_range
exists_y_fixed = y_fixed[0] <= out_of_range

def append_cross_time(l, r, time: set, contains_fixed: bool):
	for i in range(2):
		t = l[i] - r[i]
		if t >= 0:
			time.add(t if contains_fixed else t / 2)
time = {0}
if exists_l and exists_r:
	append_cross_time(l, r, time, False)
if exists_l and exists_x_fixed:
	append_cross_time(l, x_fixed, time, True)
if exists_r and exists_x_fixed:
	append_cross_time(x_fixed, r, time, True)
if exists_u and exists_d:
	append_cross_time(d, u, time, False)
if exists_d and exists_y_fixed:
	append_cross_time(d, y_fixed, time, True)
if exists_u and exists_y_fixed:
	append_cross_time(y_fixed, u, time, True)
time = list(time)
time.sort()
min_area = out_of_range * out_of_range
for t in time:
	dx = max(l[1] - t, r[1] + t, x_fixed[1]) - min(l[0] - t, r[0] + t, x_fixed[0])
	dy = max(d[1] - t, u[1] + t, y_fixed[1]) - min(d[0] - t, u[0] + t, y_fixed[0])
	min_area = min(dx * dy, min_area)
print(min_area)


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])

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)


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]))


from scipy.optimize import fmin
INF = 10 ** 18
n = int(input())
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-09, disp=False)
print(f(ans[0]))


N = int(input())
x_list = [0] * N
y_list = [0] * N
d_list = ['A'] * N
for i in range(N):
	(x, y, d) = input().split()
	x_list[i] = int(x)
	y_list[i] = int(y)
	d_list[i] = d

def _calc_tv(v_keep, v_down, v_up):
	v_0 = min([v_keep, v_down, v_up])
	if v_down == v_0:
		t_1 = 0
		t_2 = 0
		v_c = v_down
	elif v_keep == v_0:
		t_1 = 0
		t_2 = v_down - v_keep
		v_c = v_keep
	else:
		t1 = v_keep - v_up
		t2 = (v_down - v_up) / 2
		if t1 == min([t1, t2]):
			t_1 = t1
			t_2 = v_down - v_keep
			v_c = v_keep
		else:
			t_1 = (v_down - v_up) / 2
			t_2 = t_1
			v_c = (v_down + v_up) / 2
	return (t_1, t_2, v_0, v_c)

def calc_tv(v_keep, v_down, v_up, reverse=False):
	if reverse:
		(t_1, t_2, v_0, v_c) = _calc_tv(-v_keep, -v_up, -v_down)
		return (t_1, t_2, -v_0, -v_c)
	else:
		return _calc_tv(v_keep, v_down, v_up)
x_sub = [x_list[i] for i in range(N) if d_list[i] in ['D', 'U']]
if len(x_sub) > 0:
	x_min_du = min(x_sub)
	x_max_du = max(x_sub)
else:
	x_min_du = 10 ** 10
	x_max_du = -10 ** 10
x_sub = [x_list[i] for i in range(N) if d_list[i] == 'L']
if len(x_sub) > 0:
	x_min_l = min(x_sub)
	x_max_l = max(x_sub)
else:
	x_min_l = 10 ** 10
	x_max_l = -10 ** 10
x_sub = [x_list[i] for i in range(N) if d_list[i] == 'R']
if len(x_sub) > 0:
	x_min_r = min(x_sub)
	x_max_r = max(x_sub)
else:
	x_min_r = 10 ** 10
	x_max_r = -10 ** 10
(t_x_min_1, t_x_min_2, v_x_min_0, v_x_min_1) = calc_tv(x_min_du, x_min_l, x_min_r, reverse=False)
(t_x_max_1, t_x_max_2, v_x_max_0, v_x_max_1) = calc_tv(x_max_du, x_max_l, x_max_r, reverse=True)
y_sub = [y_list[i] for i in range(N) if d_list[i] in ['L', 'R']]
if len(y_sub) > 0:
	y_min_lr = min(y_sub)
	y_max_lr = max(y_sub)
else:
	y_min_lr = 10 ** 10
	y_max_lr = -10 ** 10
y_sub = [y_list[i] for i in range(N) if d_list[i] == 'D']
if len(y_sub) > 0:
	y_min_d = min(y_sub)
	y_max_d = max(y_sub)
else:
	y_min_d = 10 ** 10
	y_max_d = -10 ** 10
y_sub = [y_list[i] for i in range(N) if d_list[i] == 'U']
if len(y_sub) > 0:
	y_min_u = min(y_sub)
	y_max_u = max(y_sub)
else:
	y_min_u = 10 ** 10
	y_max_u = -10 ** 10
(t_y_min_1, t_y_min_2, v_y_min_0, v_y_min_1) = calc_tv(y_min_lr, y_min_d, y_min_u, reverse=False)
(t_y_max_1, t_y_max_2, v_y_max_0, v_y_max_1) = calc_tv(y_max_lr, y_max_d, y_max_u, reverse=True)

def calc_v(t, v_type='x_min'):
	type_ind = ['x_min', 'x_max', 'y_min', 'y_max'].index(v_type)
	t_1 = [t_x_min_1, t_x_max_1, t_y_min_1, t_y_max_1][type_ind]
	t_2 = [t_x_min_2, t_x_max_2, t_y_min_2, t_y_max_2][type_ind]
	v_0 = [v_x_min_0, v_x_max_0, v_y_min_0, v_y_max_0][type_ind]
	v_1 = [v_x_min_1, v_x_max_1, v_y_min_1, v_y_max_1][type_ind]
	c = [1, -1, 1, -1][type_ind]
	if t < t_1:
		return v_0 + c * t
	elif t < t_2:
		return v_1
	else:
		return v_1 - c * (t - t_2)

def calc_s(t):
	return (calc_v(t, 'x_max') - calc_v(t, 'x_min')) * (calc_v(t, 'y_max') - calc_v(t, 'y_min'))
t_list = [0]
t_list = t_list + [t_x_min_1, t_x_min_2]
t_list = t_list + [t_x_max_1, t_x_max_2]
t_list = t_list + [t_y_min_1, t_y_min_2]
t_list = t_list + [t_y_max_1, t_y_max_2]
res = min([calc_s(t) for t in t_list])
print(res)


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)


n = int(input())
(r, l, u, d) = [[] for _ in range(4)]
(cx_max, cx_min, cy_max, cy_min) = [None for _ in range(4)]
for i in range(n):
	(x, y, s) = input().split()
	(x, y) = (int(x), int(y))
	if s == 'R':
		r.append(x)
		if cy_max == None or cy_min == None:
			(cy_max, cy_min) = (y, y)
		(cy_max, cy_min) = (max(cy_max, y), min(cy_min, y))
	if s == 'L':
		l.append(x)
		if cy_max == None or cy_min == None:
			(cy_max, cy_min) = (y, y)
		(cy_max, cy_min) = (max(cy_max, y), min(cy_min, y))
	if s == 'U':
		u.append(y)
		if cx_max == None or cx_min == None:
			(cx_max, cx_min) = (x, x)
		(cx_max, cx_min) = (max(cx_max, x), min(cx_min, x))
	if s == 'D':
		d.append(y)
		if cx_max == None or cx_min == None:
			(cx_max, cx_min) = (x, x)
		(cx_max, cx_min) = (max(cx_max, x), min(cx_min, x))
r.sort()
l.sort()
u.sort()
d.sort()
T = [0, 10 ** 9]
for j in r + l:
	if cx_max != None:
		T.append(abs(j - cx_min))
		T.append(abs(j - cx_max))
for j in u + d:
	if cy_max != None:
		T.append(abs(j - cy_min))
		T.append(abs(j - cy_max))
try:
	for i in [r[0], r[-1]]:
		for j in [l[0], l[-1]]:
			T.append(abs(i - j) / 2)
except:
	0
try:
	for i in [u[0], u[-1]]:
		for j in [d[0], d[-1]]:
			T.append(abs(i - j) / 2)
except:
	0

def val(t):
	(xmax, xmin, ymax, ymin) = [[] for _ in range(4)]
	if u:
		ymax.append(u[-1] + t)
		ymin.append(u[0] + t)
	if d:
		ymax.append(d[-1] - t)
		ymin.append(d[0] - t)
	if cy_max != None:
		ymax.append(cy_max)
		ymin.append(cy_min)
	if r:
		xmax.append(r[-1] + t)
		xmin.append(r[0] + t)
	if l:
		xmax.append(l[-1] - t)
		xmin.append(l[0] - t)
	if cx_max != None:
		xmax.append(cx_max)
		xmin.append(cx_min)
	Y = max(ymax) - min(ymin)
	X = max(xmax) - min(xmin)
	return X * Y
ans = val(0)
for t in T:
	ans = min(ans, val(t))
print(ans)


import copy
N = int(input())
U = []
D = []
R = []
L = []
for _ in range(N):
	(x, y, ori) = input().rstrip().split(' ')
	x = int(x)
	y = int(y)
	if ori == 'U':
		U.append([x, y])
	elif ori == 'D':
		D.append([x, y])
	elif ori == 'R':
		R.append([x, y])
	else:
		L.append([x, y])

def calc(inc_points, dec_points, other_points, index):
	inc = []
	dec = []
	other = []
	if len(inc_points) > 0:
		inc_min = min([x[index] for x in inc_points])
		inc_max = max([x[index] for x in inc_points])
		inc = [inc_min, inc_max]
	if len(dec_points) > 0:
		dec_min = min([x[index] for x in dec_points])
		dec_max = max([x[index] for x in dec_points])
		dec = [dec_min, dec_max]
	if len(other_points) > 0:
		other_min = min([x[index] for x in other_points])
		other_max = max([x[index] for x in other_points])
		other = [other_min, other_max]
	cross_time = [0]
	if len(inc_points) > 0 and len(dec_points) > 0:
		for u in [inc_min, inc_max]:
			for d in [dec_min, dec_max]:
				if u < d:
					cross_time.append((d - u) / 2)
	if len(dec_points) > 0 and len(other_points) > 0:
		for rl in [other_min, other_max]:
			for d in [dec_min, dec_max]:
				if rl < d:
					cross_time.append(d - rl)
	if len(inc_points) > 0 and len(other_points) > 0:
		for rl in [other_min, other_max]:
			for u in [inc_min, inc_max]:
				if u < rl:
					cross_time.append(rl - u)
	return (inc, dec, other, cross_time)

def calc_size(inc, dec, other, times):
	sizes = []
	for time in times:
		values = copy.copy(other)
		if len(inc) > 0:
			values.extend([x + time for x in inc])
		if len(dec) > 0:
			values.extend([x - time for x in dec])
		sizes.append(max(values) - min(values))
	return sizes
(inc_x, dec_x, other_x, cross_time_x) = calc(R, L, U + D, 0)
(inc_y, dec_y, other_y, cross_time_y) = calc(U, D, R + L, 1)
times = list(set(cross_time_x + cross_time_y))
sizes_x = calc_size(inc_x, dec_x, other_x, times)
sizes_y = calc_size(inc_y, dec_y, other_y, times)
print(min([x * y for (x, y) in zip(sizes_x, sizes_y)]))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import itertools
INF = 10 ** 18
data = {x: [-INF, INF, -INF, INF] for x in 'RLUD'}
N = int(readline())
XYD = read().split()
X = (int(x) for x in XYD[::3])
Y = (int(x) for x in XYD[1::3])
D = (x.decode('utf-8') for x in XYD[2::3])
for (x, y, d) in zip(X, Y, D):
	if data[d][0] < x:
		data[d][0] = x
	if data[d][1] > x:
		data[d][1] = x
	if data[d][2] < y:
		data[d][2] = y
	if data[d][3] > y:
		data[d][3] = y
X = []
Y = []
X += [(data['L'][0], -1), (data['L'][1], -1)]
X += [(data['R'][0], 1), (data['R'][1], 1)]
X += [(data['U'][0], 0), (data['U'][1], 0)]
X += [(data['D'][0], 0), (data['D'][1], 0)]
Y += [(data['L'][2], 0), (data['L'][3], 0)]
Y += [(data['R'][2], 0), (data['R'][3], 0)]
Y += [(data['U'][2], 1), (data['U'][3], 1)]
Y += [(data['D'][2], -1), (data['D'][3], -1)]
X = [(x, dx) for (x, dx) in X if abs(x) < INF]
Y = [(x, dx) for (x, dx) in Y if abs(x) < INF]
T = []
for ((x, dx), (y, dy)) in itertools.combinations(X, 2):
	if dx == dy:
		continue
	T.append((x - y) / (dy - dx))
for ((x, dx), (y, dy)) in itertools.combinations(Y, 2):
	if dx == dy:
		continue
	T.append((x - y) / (dy - dx))
T = set([0] + [t for t in T if t > 0])

def F(t):
	xs = [x + t * speed for (x, speed) in X]
	ys = [x + t * speed for (x, speed) in Y]
	dx = max(xs) - min(xs)
	dy = max(ys) - min(ys)
	return dx * dy
answer = min((F(t) for t in T))
print(answer)


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 = []
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])
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])
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])
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)


import sys
input = sys.stdin.readline
N = int(input())
a = []
l = []
r = []
lr = []
u = []
d = []
ud = []
for _ in range(N):
	(x, y, w) = input().split()
	(x, y) = map(int, (x, y))
	a.append((x, y, w))
	if w == 'L':
		l.append(x)
		ud.append(y)
	if w == 'R':
		r.append(x)
		ud.append(y)
	if w == 'U':
		u.append(y)
		lr.append(x)
	if w == 'D':
		d.append(y)
		lr.append(x)
l.sort()
r.sort()
lr.sort()
u.sort()
d.sort()
ud.sort()
t = [0]
if len(l):
	if len(r):
		t.append((l[-1] - r[-1]) / 2)
	if len(lr):
		t.append(l[-1] - lr[-1])
		t.append(l[0] - lr[0])
if len(r):
	if len(l):
		t.append((l[0] - r[0]) / 2)
	if len(lr):
		t.append(lr[0] - r[0])
		t.append(lr[-1] - r[-1])
if len(d):
	if len(u):
		t.append((d[-1] - u[-1]) / 2)
	if len(ud):
		t.append(d[-1] - ud[-1])
		t.append(d[0] - ud[0])
if len(u):
	if len(d):
		t.append((d[0] - u[0]) / 2)
	if len(ud):
		t.append(ud[0] - u[0])
		t.append(ud[-1] - u[-1])
t = sorted(set(t), reverse=True)
while t[-1] < 0:
	t.pop()

def solve(tt):
	ll = float('inf')
	rr = -float('inf')
	uu = -float('inf')
	dd = float('inf')
	for (x, y, w) in a:
		xx = x
		yy = y
		if w == 'L':
			xx -= tt
		if w == 'R':
			xx += tt
		if w == 'U':
			yy += tt
		if w == 'D':
			yy -= tt
		ll = min(ll, xx)
		rr = max(rr, xx)
		uu = max(uu, yy)
		dd = min(dd, yy)
	return (rr - ll) * (uu - dd)
res = float('inf')
for tt in t:
	res = min(res, solve(tt))
print(res)


import sys
sys.setrecursionlimit(10 ** 7)
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right
from collections import deque, defaultdict
from collections import Counter
from itertools import accumulate, combinations, permutations, product
from heapq import heapify, heappop, heappush
from functools import reduce, lru_cache
from decimal import Decimal

def input():
	x = sys.stdin.readline()
	return x[:-1] if x[-1] == '\n' else x

def printe(*x):
	print('## ', *x, file=sys.stderr)

def printl(li):
	_ = print(*li, sep='\n') if li else None

def argsort(s, return_sorted=False):
	inds = sorted(range(len(s)), key=lambda k: s[k])
	if return_sorted:
		return (inds, [s[i] for i in inds])
	return inds

def alp2num(c, cap=False):
	return ord(c) - 97 if not cap else ord(c) - 65

def num2alp(i, cap=False):
	return chr(i + 97) if not cap else chr(i + 65)

def matmat(A, B):
	(K, N, M) = (len(B), len(A), len(B[0]))
	return [[sum([A[i][k] * B[k][j] for k in range(K)]) for j in range(M)] for i in range(N)]

def matvec(M, v):
	(N, size) = (len(v), len(M))
	return [sum([M[i][j] * v[j] for j in range(N)]) for i in range(size)]

def T(M):
	(n, m) = (len(M), len(M[0]))
	return [[M[j][i] for j in range(n)] for i in range(m)]

def main():
	mod = 1000000007
	N = int(input())
	S = []
	for i in range(N):
		(x, y, d) = input().split()
		x = int(x)
		y = int(y)
		S.append((x, y, d))
	sx = sorted(S, key=itemgetter(0))
	sy = sorted(S, key=itemgetter(1))
	ts = set([0])
	minx = sx[0][0]
	f1 = 0
	f2 = 0
	for s in sx:
		if s[2] == 'L' and (not f1):
			if sx[0][2] == 'R':
				ts.add((s[0] - minx) * 0.5)
			else:
				ts.add(s[0] - minx)
			f1 = 1
		elif s[2] in ('U', 'D') and (not f2):
			ts.add(s[0] - minx)
			f2 = 1
		if f1 and f2:
			break
	maxx = sx[-1][0]
	f1 = 0
	f2 = 0
	for s in reversed(sx):
		if s[2] == 'R' and (not f1):
			if sx[0][2] == 'L':
				ts.add(abs(s[0] - maxx) * 0.5)
			else:
				ts.add(abs(s[0] - maxx))
			f1 = 1
		elif s[2] in ('U', 'D') and (not f2):
			ts.add(abs(s[0] - maxx))
			f2 = 1
		if f1 and f2:
			break
	minx = sy[0][1]
	f1 = 0
	f2 = 0
	for s in sy:
		if s[2] == 'D' and (not f1):
			if sy[1][2] == 'U':
				ts.add((s[1] - minx) * 0.5)
			else:
				ts.add(s[1] - minx)
			f1 = 1
		elif s[2] in ('L', 'R') and (not f2):
			ts.add(s[1] - minx)
			f2 = 1
		if f1 and f2:
			break
	maxx = sy[-1][1]
	f1 = 0
	f2 = 0
	for s in reversed(sy):
		if s[2] == 'U' and (not f1):
			if sx[1][2] == 'D':
				ts.add(abs(s[1] - maxx) * 0.5)
			else:
				ts.add(abs(s[1] - maxx))
			f1 = 1
		elif s[2] in ('L', 'R') and (not f2):
			ts.add(abs(s[1] - maxx))
			f2 = 1
		if f1 and f2:
			break

	def calc(t):
		minx = 10 ** 9
		maxx = -10 ** 9
		miny = 10 ** 9
		maxy = -10 ** 9
		for s in S:
			(x, y, d) = s
			if d == 'U':
				y += t
			elif d == 'D':
				y -= t
			elif d == 'L':
				x -= t
			elif d == 'R':
				x += t
			minx = min(minx, x)
			miny = min(miny, y)
			maxx = max(maxx, x)
			maxy = max(maxy, y)
		return (maxx - minx) * (maxy - miny)
	ans = 10 ** 17
	for t in ts:
		ans = min(ans, calc(t))
	for (t1, t2) in combinations(ts, 2):
		mid = (t1 + t2) * 0.5
		ans = min(ans, calc(mid))
	print(ans)
main()


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')
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)


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())


n = int(input())
xyd = [input().split() for _ in range(n)]
x_max_RL_ = [-200000000.0] * 3
x_min_RL_ = [200000000.0] * 3
y_max_UD_ = [-200000000.0] * 3
y_min_UD_ = [200000000.0] * 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:
		(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]) <= 100000000.0:
			for j in range(i + 1, 3):
				if abs(_max_min[j]) <= 100000000.0:
					cross = (_max_min[i] - _max_min[j]) / (j - i)
					if cross > 0:
						kouho_time.add(cross)
ans = 4e+16
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]) <= 100000000.0))
	x_min = min((x_min_RL_[i] + t * (i - 1) for i in range(3) if abs(x_min_RL_[i]) <= 100000000.0))
	y_max = max((y_max_UD_[i] + t * (i - 1) for i in range(3) if abs(y_max_UD_[i]) <= 100000000.0))
	y_min = min((y_min_UD_[i] + t * (i - 1) for i in range(3) if abs(y_min_UD_[i]) <= 100000000.0))
	ans = min(ans, (x_max - x_min) * (y_max - y_min))
print(ans)


import sys
input = sys.stdin.readline
inf = 10 ** 9
n = int(input())
if n == 1:
	print(0)
	exit()
UD_x = [inf, -1 * inf]
LR_y = [inf, -1 * inf]
U_y = [inf, -1 * inf]
D_y = [inf, -1 * inf]
R_x = [inf, -1 * inf]
L_x = [inf, -1 * inf]
for i in range(n):
	tmp = input().split()
	(x, y) = map(int, tmp[:2])
	d = tmp[2]
	if d == 'U':
		UD_x[0] = min(UD_x[0], x)
		UD_x[1] = max(UD_x[1], x)
		U_y[0] = min(U_y[0], y)
		U_y[1] = max(U_y[1], y)
	elif d == 'D':
		UD_x[0] = min(UD_x[0], x)
		UD_x[1] = max(UD_x[1], x)
		D_y[0] = min(D_y[0], y)
		D_y[1] = max(D_y[1], y)
	elif d == 'R':
		LR_y[0] = min(LR_y[0], y)
		LR_y[1] = max(LR_y[1], y)
		R_x[0] = min(R_x[0], x)
		R_x[1] = max(R_x[1], x)
	elif d == 'L':
		LR_y[0] = min(LR_y[0], y)
		LR_y[1] = max(LR_y[1], y)
		L_x[0] = min(L_x[0], x)
		L_x[1] = max(L_x[1], x)
x_dif = max(UD_x[1], R_x[1], L_x[1]) - min(UD_x[0], R_x[0], L_x[0])
y_dif = max(LR_y[1], U_y[1], D_y[1]) - min(LR_y[0], U_y[0], D_y[0])
ans = x_dif * y_dif
check = []
if D_y != [inf, -1 * inf]:
	for (meet, speed) in zip([LR_y[0], U_y[0]], [1, 2]):
		tmp = (D_y[0] - meet) / speed
		if tmp > 0:
			check.append(tmp)
	for (meet, speed) in zip([LR_y[1], U_y[1]], [1, 2]):
		tmp = (D_y[1] - meet) / speed
		if tmp > 0:
			check.append(tmp)
if D_y != [inf, -1 * inf]:
	for (meet, speed) in zip([LR_y[0], U_y[0]], [1, 2]):
		tmp = (D_y[0] - meet) / speed
		if tmp > 0:
			check.append(tmp)
	for (meet, speed) in zip([LR_y[1], U_y[1]], [1, 2]):
		tmp = (D_y[1] - meet) / speed
		if tmp > 0:
			check.append(tmp)
if U_y != [inf, -1 * inf]:
	for (meet, speed) in zip([LR_y[0], D_y[0]], [1, 2]):
		tmp = (meet - U_y[0]) / speed
		if tmp > 0:
			check.append(tmp)
	for (meet, speed) in zip([LR_y[1], D_y[1]], [1, 2]):
		tmp = (meet - U_y[1]) / speed
		if tmp > 0:
			check.append(tmp)
if L_x != [inf, -1 * inf]:
	for (meet, speed) in zip([UD_x[0], R_x[0]], [1, 2]):
		tmp = (L_x[0] - meet) / speed
		if tmp > 0:
			check.append(tmp)
	for (meet, speed) in zip([UD_x[1], R_x[1]], [1, 2]):
		tmp = (L_x[1] - meet) / speed
		if tmp > 0:
			check.append(tmp)
if R_x != [inf, -1 * inf]:
	for (meet, speed) in zip([UD_x[0], L_x[0]], [1, 2]):
		tmp = (meet - R_x[0]) / speed
		if tmp > 0:
			check.append(tmp)
	for (meet, speed) in zip([UD_x[1], L_x[1]], [1, 2]):
		tmp = (meet - R_x[1]) / speed
		if tmp > 0:
			check.append(tmp)
for sec in check:
	x_dif = max(UD_x[1], R_x[1] + sec, L_x[1] - sec) - min(UD_x[0], R_x[0] + sec, L_x[0] - sec)
	y_dif = max(LR_y[1], U_y[1] + sec, D_y[1] - sec) - min(LR_y[0], U_y[0] + sec, D_y[0] - sec)
	ans = min(ans, x_dif * y_dif)
print(ans)


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 di(t):
	a = 1
	return calc(t + a) - calc(t - a)

def dii(t):
	a = 1e-07
	return calc(t + a) - calc(t - a)
l = 0
r = 10 ** 10
for _ in range(100):
	m = (l + r) // 2
	if di(m) > 0:
		r = m
	else:
		l = m
for _ in range(100):
	m = (l + r) / 2
	if dii(m) > 0:
		r = m
	else:
		l = m
print(calc(m))


def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	inf = 2 * 10 ** 9
	L = [inf, inf, inf]
	R = [-inf, -inf, -inf]
	U = [-inf, -inf, -inf]
	D = [inf, inf, inf]
	for _ in range(N):
		(x, y, d) = input().split()
		x = int(x) * 2
		y = int(y) * 2
		if d == 'L':
			L[0] = min(L[0], x)
			R[1] = max(R[1], x)
			U[2] = max(U[2], y)
			D[2] = min(D[2], y)
		elif d == 'R':
			L[1] = min(L[1], x)
			R[0] = max(R[0], x)
			U[2] = max(U[2], y)
			D[2] = min(D[2], y)
		elif d == 'U':
			L[2] = min(L[2], x)
			R[2] = max(R[2], x)
			U[0] = max(U[0], y)
			D[1] = min(D[1], y)
		else:
			L[2] = min(L[2], x)
			R[2] = max(R[2], x)
			U[1] = max(U[1], y)
			D[0] = min(D[0], y)

	def calc(t):
		if t < 0:
			return 10 ** 20
		xmin = min(L[0] - t, L[1] + t, L[2])
		xmax = max(R[0] + t, R[1] - t, R[2])
		ymax = max(U[0] + t, U[1] - t, U[2])
		ymin = min(D[0] - t, D[1] + t, D[2])
		return (xmax - xmin) * (ymax - ymin)
	ans = calc(0)
	ans = min(ans, calc((L[0] - L[1]) // 2), calc(L[0] - L[2]), calc(L[2] - L[1]))
	ans = min(ans, calc((R[1] - R[0]) // 2), calc(R[2] - R[0]), calc(R[1] - R[2]))
	ans = min(ans, calc((U[1] - U[0]) // 2), calc(U[2] - U[0]), calc(U[1] - U[2]))
	ans = min(ans, calc((D[0] - D[1]) // 2), calc(D[0] - D[2]), calc(D[2] - D[1]))
	print(ans / 4)
main()