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

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

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

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


if __name__ == '__main__':
    main()

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

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

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





if __name__ == "__main__":
    main()

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

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

Solution (Python):
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):
    """時刻tにおける面積sを求める"""
    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)

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

if __name__ == '__main__':
    examB()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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

Solution (Python):
from itertools import chain
n = int(input())

p = [[] for _ in range(4)]
for _ in range(n):
    a, b, d = input().split()
    a, b = map(int, (a, b))
    p[0 if d == 'R' else 1 if d == 'L' else 2 if d == 'U' else 3].append((a, b))
to_min = [None] * 4
to_max = [None] * 4
for i in range(4):
    if p[i]:
        to_min[i] = (max if i & 1 else min)(a if i < 2 else b for a, b in p[i])
        to_max[i] = (min if i & 1 else max)(a if i < 2 else b for a, b in p[i])
still = [None] * 2
for i in range(2):
    j = (1-i)*2
    if p[j] or p[j + 1]:
        still[i] = min(b if i else a for a, b in chain(p[j], p[j+1])), max(b if i else a for a, b in chain(p[j], p[j+1])) 

def f_width(i, t):
    if still[i]:
        leftmost, rightmost = still[i]
    else:
        leftmost, rightmost = 10 ** 18, - 10 ** 18
    i *= 2
    if to_min[i] != None:
        leftmost = min(leftmost, to_min[i] + t)
    if to_max[i+1] != None:
        leftmost = min(leftmost, to_max[i+1] - t)
    if to_min[i+1] != None:
        rightmost = max(rightmost, to_min[i+1] - t)
    if to_max[i] != None:
        rightmost = max(rightmost, to_max[i] + t)
    return rightmost - leftmost

t = []
for i in range(2):
    l, r = 0, 10 ** 10
    cnt = 0
    while cnt < 100000:
        cnt += 1
        c1, c2 = l + (r - l) / 3, l + (r - l) * 2 / 3
        if f_width(i, c1) >= f_width(i, c2):
            l = c1
        else:
            r = c2
    t.append(l)
l, r = min(t), max(t)
cnt = 0
while cnt < 100000:
    cnt += 1
    c1, c2 = l + (r - l) / 3, l + (r - l) * 2 / 3
    if f_width(0, c1) * f_width(1, c1) > f_width(0, c2) * f_width(1, c2):
        l = c1
    else:
        r = c2
print('{0:.13f}'.format(f_width(0, l) * f_width(1, l)))