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

Solution (Python):
from collections import defaultdict
N=int(input())

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

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

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

cand_time_x=cand_time(list(xset))
cand_time_y=cand_time(list(yset))

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 xset:
    pos_min_x=min(pos_min_x,get_pos(x2,t))
    pos_max_x=max(pos_max_x,get_pos(x2,t))
    
  pos_min_y=float("inf")
  pos_max_y=-float("inf")
  for y2 in yset:
    pos_min_y=min(pos_min_y,get_pos(y2,t))
    pos_max_y=max(pos_max_y,get_pos(y2,t))

  
  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)

Solution (Python):
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
      else:
        if d2==-1:
          t=(p2-p1)/2
        else:
          t=p2-p1
       
      if t>0:
        ret.add(t)
  return ret

cand_time_x=cand_time(xlist2)
cand_time_y=cand_time(ylist2)

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)

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

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


if __name__ == "__main__":
    main()

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

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

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


if __name__ == '__main__':
    main()

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

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

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

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

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

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

Solution (Python):

from itertools import combinations

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

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

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


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

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

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


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

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

    return dx * dy


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

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