Problem:
 Score : 600 points    Problem Statement 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 1 2
0 3 D
3 0 L      Sample Output 1 0  After three seconds, the two points will meet at the origin. The value in question will be 0 at that moment.       Sample Input 2 5
-7 -10 U
7 -6 U
-8 7 D
-3 3 D
0 -6 R      Sample Output 2 97.5  The answer may not be an integer.       Sample Input 3 20
6 -10 R
-4 -9 U
9 6 D
-3 -2 R
0 7 D
4 5 D
10 -10 U
-1 -8 U
10 -6 D
8 -5 U
6 4 D
0 3 D
7 9 R
9 -4 R
3 10 D
1 9 U
1 -6 U
9 -8 R
6 7 D
7 -3 D      Sample Output 3 273

Solution (Python):
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]))

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):
N = int(input())

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

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

T = [0]
INF = 10**9

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

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

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

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

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

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


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

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

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

kouho_time = set([0])

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


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

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

print(ans)

Solution (Python):
import queue

"""
N = int(input())



A = []
for i in range(N):
	A.append(int(input()))

print(A)

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

N = int(input())

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

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

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

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

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

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

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

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

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


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

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

print(min_ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):

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

Solution (Python):
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())

Solution (Python):
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)