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

if __name__ == '__main__':
    main()

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

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


if __name__ == '__main__':
    print(main())

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

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

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

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






T = set()
T.add(0)
for v in vars:
    u, d, c1, c2 = ('R', 'L', 'U', 'D') if v.startswith('x') else \
                   ('U', 'D', 'R', 'L')
    C  = maxmin[v[-3:]](S[c1][v], S[c2][v])
    t1 =  S[d][v] - C
    t2 = -S[u][v] + C
    t3 = (S[d][v] - S[u][v]) / 2
    T.update([t1, t2, t3])

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

print(q)

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

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

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

Solution (Python):


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

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

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

Solution (Python):



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

Solution (Python):


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)


if __name__ == '__main__':
    main()

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

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

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

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