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


def check(t):
    maxx = max(ud_maxx, r_maxx + t, l_maxx - t)
    minx = min(ud_minx, r_minx + t, l_minx - t)
    maxy = max(lr_maxy, u_maxy + t, d_maxy - t)
    miny = min(lr_miny, u_miny + t, d_miny - t)
    return (maxx - minx) * (maxy - miny)


n = int(input())
lr_maxy, lr_miny, ud_maxx, ud_minx = -1e9, 1e9, -1e9, 1e9
l_maxx, l_minx, r_maxx, r_minx = -1e9, 1e9, -1e9, 1e9
u_maxy, u_miny, d_maxy, d_miny = -1e9, 1e9, -1e9, 1e9
for line in sys.stdin:
    x, y, d = line.rstrip().split()
    x, y = int(x), int(y)
    if d == 'L':
        lr_maxy = max(lr_maxy, y)
        lr_miny = min(lr_miny, y)
        l_maxx = max(l_maxx, x)
        l_minx = min(l_minx, x)
    elif d == 'R':
        lr_maxy = max(lr_maxy, y)
        lr_miny = min(lr_miny, y)
        r_maxx = max(r_maxx, x)
        r_minx = min(r_minx, x)
    elif d == 'U':
        ud_maxx = max(ud_maxx, x)
        ud_minx = min(ud_minx, x)
        u_maxy = max(u_maxy, y)
        u_miny = min(u_miny, y)
    else:
        ud_maxx = max(ud_maxx, x)
        ud_minx = min(ud_minx, x)
        d_maxy = max(d_maxy, y)
        d_miny = min(d_miny, y)

inflections = {0}
inflections.add(max(0, l_maxx - ud_maxx))
inflections.add(max(0, (l_maxx - r_maxx) / 2))
inflections.add(max(0, ud_maxx - r_maxx))
inflections.add(max(0, l_minx - ud_minx))
inflections.add(max(0, (l_minx - r_minx) / 2))
inflections.add(max(0, ud_minx - r_minx))

inflections.add(max(0, d_maxy - lr_maxy))
inflections.add(max(0, (d_maxy - u_maxy) / 2))
inflections.add(max(0, lr_maxy - u_maxy))
inflections.add(max(0, d_miny - lr_miny))
inflections.add(max(0, (d_miny - u_miny) / 2))
inflections.add(max(0, lr_miny - u_miny))

print(min(map(check, inflections)))

Solution (Python):
N = int(input())
Xmi, Xma, Ymi, Yma, DYmi, DYma, UYmi, UYma, RXmi, RXma, LXmi, LXma = [(10**10), -(10**10)] * 6
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    
    if d == "R":
        RXmi = min(RXmi, x)
        RXma = max(RXma, x)
    elif d == "L":
        LXmi = min(LXmi, x)
        LXma = max(LXma, x)
    else:
        Xmi = min(Xmi, x)
        Xma = max(Xma, x)
        
    if d == "U":
        UYmi = min(UYmi, y)
        UYma = max(UYma, y)
    elif d == "D":
        DYmi = min(DYmi, y)
        DYma = max(DYma, y)
    else:
        Ymi = min(Ymi, y)
        Yma = max(Yma, y)

def calc(t):
    xmi = min(RXmi+t, LXmi-t, Xmi)
    xma = max(RXma+t, LXma-t, Xma)
    ymi = min(UYmi+t, DYmi-t, Ymi)
    yma = max(UYma+t, DYma-t, Yma)
    return max(yma-ymi, 0)*max(xma-xmi, 0)

mi = 10**20
import random
import time
sTime = time.time()
while time.time()-sTime < 4.5:
    l = 0
    r = 10**(random.randrange(10000)/1000)
    for _ in range(100):
        m1 = (l*2+r)/3
        m2 = (l+r*2)/3
        if calc(m1) > calc(m2):
            l = m1
        else:
            r = m2
    mi = min(mi, calc(m1))


print(mi)

Solution (Python):
import random
import bisect
import math

option = 0  
max_or_min = 0  
filewrite = 0  
dimension = 1
iter = 1

N = 100  
T = 5000  
maximum = 10 ** 12
minimum = 0

n = int(input())
x_left = []
x_right = []
y_up = []
y_down = []
x_const = []
y_const = []
for i in range(n):
    x, y, d = input().split()
    x = int(x)
    y = int(y)
    if d == "U":
        x_const.append(x)
        y_up.append(y)
    elif d == "D":
        x_const.append(x)
        y_down.append(y)
    elif d == "L":
        y_const.append(y)
        x_left.append(x)
    elif d == "R":
        y_const.append(y)
        x_right.append(x)

x_const.sort()
y_const.sort()
x_left.sort()
x_right.sort()
y_up.sort()
y_down.sort()

try:
    x_const_max = x_const[-1]
    x_const_min = x_const[0]
except:
    x_const_max = -float("inf")
    x_const_min = float("inf")

try:
    y_const_max = y_const[-1]
    y_const_min = y_const[0]
except:
    y_const_max = -float("inf")
    y_const_min = float("inf")

try:
    x_left_max = x_left[-1]
    x_left_min = x_left[0]
except:
    x_left_max = -float("inf")
    x_left_min = float("inf")

try:
    x_right_max = x_right[-1]
    x_right_min = x_right[0]
except:
    x_right_max = -float("inf")
    x_right_min = float("inf")

try:
    y_up_max = y_up[-1]
    y_up_min = y_up[0]
except:
    y_up_max = -float("inf")
    y_up_min = float("inf")

try:
    y_down_max = y_down[-1]
    y_down_min = y_down[0]

except:
    y_down_max = -float("inf")
    y_down_min = float("inf")





def criterion(x, x_min, x_max):
    z = 0
    i = x[0]
    max_x = max(x_const_max, x_left_max - i, x_right_max + i)
    min_x = min(x_const_min, x_left_min - i, x_right_min + i)
    max_y = max(y_const_max, y_down_max - i, y_up_max + i)
    min_y = min(y_const_min, y_down_min - i, y_up_min + i)
    z = (max_x - min_x) * (max_y - min_y)
    if x < x_min:
        z = float("inf")
    return z



def update_position(x, v):
    new_x = [x[i] + v[i] for i in range(dimension)]
    return new_x



def update_velocity(x, v, p, g, w, ro_max=1.0, c1=1.6, c2=1.6):
    
    phi = c1 + c2
    K = 2 / abs(2 - phi - (phi * phi - 4 * phi) ** 0.5)

    
    if option != 0:
        new_v = [K * (w * v[i] + c1 * random.uniform(0, ro_max) * (p[i] - x[i]) + c2 * random.uniform(0, ro_max) * (
                    g[i] - x[i])) for i in range(dimension)]
    else:
        new_v = [
            w * v[i] + c1 * random.uniform(0, ro_max) * (p[i] - x[i]) + c2 * random.uniform(0, ro_max) * (g[i] - x[i])
            for i in range(dimension)]

    return new_v


def main():
    w = 0.5
    w_best, w_worst = 1.25, 0.25
    x_min = [minimum for i in range(dimension)]
    x_max = [maximum for i in range(dimension)]

    
    ps = [[random.uniform(x_min[j], x_max[j]) for j in range(dimension)] for i in range(N)]
    vs = [[0.0 for j in range(dimension)] for i in range(N)]

    personal_best_positions = list(ps)
    personal_best_scores = [criterion(p, x_min, x_max) for p in ps]
    best_particle = personal_best_scores.index(max(personal_best_scores))
    global_best_position = personal_best_positions[best_particle]

    for t in range(T):
        for n in range(N):
            x = ps[n]
            v = vs[n]
            p = personal_best_positions[n]

            if option >= 2:
                best_list = sorted(personal_best_positions)
                mu = bisect.bisect_left(best_list, p) + 1
                w = w_best - mu * (w_best - w_worst) / (N - 1)

            
            new_x = update_position(x, v)
            ps[n] = new_x

            
            new_v = update_velocity(new_x, v, p, global_best_position, w)
            vs[n] = new_v

            
            score = criterion(new_x, x_min, x_max)

            if max_or_min == 1:
                if score > personal_best_scores[n]:
                    personal_best_scores[n] = score
                    personal_best_positions[n] = new_x
            elif max_or_min == 0:
                if score < personal_best_scores[n]:
                    personal_best_scores[n] = score
                    personal_best_positions[n] = new_x

        
        if max_or_min == 1:
            if filewrite >= 1: f.write(str(max(personal_best_scores)) + "\n")
            best_particle = personal_best_scores.index(max(personal_best_scores))
            global_best_position = personal_best_positions[best_particle]

        elif max_or_min == 0:
            if filewrite >= 1: f.write(str(min(personal_best_scores)) + "\n")
            best_particle = personal_best_scores.index(min(personal_best_scores))
            global_best_position = personal_best_positions[best_particle]

    
    

    
    if max_or_min == 1:
        return max(personal_best_scores)
    elif max_or_min == 0:
        
        return min(personal_best_scores)




if max_or_min == 1:
    best = -float("inf")
    for i in range(iter):
        if filewrite >= 2: option = i
        if filewrite >= 1:
            with open('result_' + str(option) + ".txt", 'w') as f:
                best = max(best, main())
        else:
            best = max(best, main())

elif max_or_min == 0:
    best = float("inf")
    for i in range(iter):
        if filewrite >= 2: option = i
        if filewrite >= 1:
            with open('result_' + str(option) + ".txt", 'w') as f:
                best = min(best, main())
        else:
            best = min(best, main())

print(best)

Solution (Python):
N = int(input())
 
PS = [[], [], [], []]
S = "RLUD".index
 
for i in range(N):
    x, y, d = input().split(); x = int(x); y = int(y)
    PS[S(d)].append((x, y))
 
T = [0]
INF = 10**9
 
dymin = INF; dymax = -INF
P = []
for i in [0, 1]:
    xmin = INF; xmax = -INF
    for x, y in PS[i]:
        dymin = min(dymin, y)
        dymax = max(dymax, y)
        xmin = min(xmin, x)
        xmax = max(xmax, x)
    P.append((xmin, xmax))
for x0 in P[0]:
    for x1 in P[1]:
        T.append(max(x1 - x0, 0) / 2.)
 
dxmin = INF; dxmax = -INF
Q = []
for i in [2, 3]:
    ymin = INF; ymax = -INF
    for x, y in PS[i]:
        dxmin = min(dxmin, x)
        dxmax = max(dxmax, x)
        ymin = min(ymin, y)
        ymax = max(ymax, y)
    Q.append((ymin, ymax))
for y0 in Q[0]:
    for y1 in Q[1]:
        T.append(max(y1 - y0, 0) / 2.)
 
for x0 in [dxmin, dxmax]:
    for x in P[0]:
        T.append(max(x0 - x, 0))
    for x in P[1]:
        T.append(max(x - x0, 0))
for y0 in [dymin, dymax]:
    for y in Q[0]:
        T.append(max(y0 - y, 0))
    for y in Q[1]:
        T.append(max(y - y0, 0))
 
ans = 10**30
for t in T:
    xmin = dxmin; xmax = dxmax
    ymin = dymin; ymax = dymax
 
    xi, xa = P[0]
    if xi != INF:
        xmin = min(xmin, xi+t)
        xmax = max(xmax, xa+t)
    xi, xa = P[1]
    if xi != INF:
        xmin = min(xmin, xi-t)
        xmax = max(xmax, xa-t)
    yi, ya = Q[0]
    if yi != INF:
        ymin = min(ymin, yi+t)
        ymax = max(ymax, ya+t)
    yi, ya = Q[1]
    if yi != INF:
        ymin = min(ymin, yi-t)
        ymax = max(ymax, ya-t)
    ans = min(ans, (xmax - xmin) * (ymax - ymin))
print("%.6f" % ans)

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 > max(MRp, MRm):
	t.append(MR - MRp)
elif MRm + MRp >= 2 * MR and MRm > MRp:
	t.append((MRm - MRp) / 2)
elif MRm > MRp:
	t.append(MRm - MR)
	t.append(MR - MRp)	
if mR < min(mRp, mRm):
	t.append(mRm - mR)
elif mRm + mRp <= 2 * mR and mRm > mRp:
	t.append((mRm - mRp) / 2)
elif mRm > mRp:
	t.append(mRm - mR)
	t.append(mR - mRp)
if MU > max(MUp, MUm):
	t.append(MU - MUp)
elif MUm + MUp >= 2 * MU and MUm > MUp:
	t.append((MUm - MUp) / 2)
elif MUm > MUp:
	t.append(MUm - MU)
	t.append(MU - MUp)
if mU < min(mUp, mUm):
	t.append(mUm - mU)
elif mUm + mUp <= 2 * mU and mUm > mUp:
	t.append((mUm - mUp) / 2)
elif mUm > mUp:
	t.append(mUm - mU)
	t.append(mU - mUp)

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

Solution (Python):
import sys
input=sys.stdin.readline
from itertools import product
n=int(input())
Rx,Ry,Lx,Ly,Ux,Uy,Dx,Dy=[],[],[],[],[],[],[],[]
for _ in range(n):
    x,y,d=input().split()
    x=int(x); y=int(y)
    if d=='R':
        Rx.append(x); Ry.append(y)
    elif d=='L':
        Lx.append(x); Ly.append(y)
    elif d=='U':
        Ux.append(x); Uy.append(y)
    else:
        Dx.append(x); Dy.append(y)
inf=float('inf')
stay_x=[min(Ux+Dx+[inf]),max(Ux+Dx+[-inf])]
plus_x=[min(Rx+[inf]),max(Rx+[-inf])]
minus_x=[min(Lx+[inf]),max(Lx+[-inf])]
plus_y=[min(Uy+[inf]),max(Uy+[-inf])]
minus_y=[min(Dy+[inf]),max(Dy+[-inf])]
stay_y=[min(Ly+Ry+[inf]),max(Ly+Ry+[-inf])]

T=[0]
for x1,x2 in product(minus_x,plus_x):
    if x1 in (-inf,inf) or x2 in (-inf,inf):
        continue
    t=(x1-x2)/2
    if t>0:
        T.append(t)
for x1,x2 in product(minus_x,stay_x):
    if x1 in (-inf,inf) or x2 in (-inf,inf):
        continue
    t=x1-x2
    if t>0:
        T.append(t)
for x1,x2 in product(plus_x,stay_x):
    if x1 in (-inf,inf) or x2 in (-inf,inf):
        continue
    t=x2-x1
    if t>0:
        T.append(t)
for y1,y2 in product(minus_y,plus_y):
    if y1 in (-inf,inf) or y2 in (-inf,inf):
        continue
    t=(y1-y2)/2
    if t>0:
        T.append(t)
for y1,y2 in product(minus_y,stay_y):
    if y1 in (-inf,inf) or y2 in (-inf,inf):
        continue
    t=y1-y2
    if t>0:
        T.append(t)
for y1,y2 in product(plus_y,stay_y):
    if y1 in (-inf,inf) or y2 in (-inf,inf):
        continue
    t=y2-y1
    if t>0:
        T.append(t)
T=sorted(set(T))
T.append(10**10)

def width(t):
    left=min(stay_x[0],plus_x[0]+t,minus_x[0]-t)
    right=max(stay_x[1],plus_x[1]+t,minus_x[1]-t)
    return right-left
def height(t):
    down=min(stay_y[0],plus_y[0]+t,minus_y[0]-t)
    up=max(stay_y[1],plus_y[1]+t,minus_y[1]-t)
    return up-down

def minS(x1,x2,y1,y2):
    ax,bx=x2-x1,x1; ay,by=y2-y1,y1
    a,b,c=ax*ay,ax*by+bx*ay,bx*by
    if a<=0:
        return min(x1*y1,x2*y2)
    m=-b/(2*a)
    if m<0 or m>1:
        return min(x1*y1,x2*y2)
    return a*m**2+b*m+c

l=len(T)
X=[width(t) for t in T]
Y=[height(t) for t in T]
ans=inf
for i in range(l-1):
    x1,x2=X[i],X[i+1]
    y1,y2=Y[i],Y[i+1]
    ans=min(ans,minS(x1,x2,y1,y2))
print(ans)

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 == 'L':
    X[-1].append(x)
    Y[0].append(y)
  elif d == 'R':
    X[1].append(x)
    Y[0].append(y)
  elif d == 'U':
    Y[1].append(y)
    X[0].append(x)
  else:
    Y[-1].append(y)
    X[0].append(x)

for i in [-1,0,1]:
  X[i] = [min(X[i] + [INF]), max(X[i] + [-INF])]
  Y[i] = [min(Y[i] + [INF]), max(Y[i] + [-INF])]

def calc_width(t, X):
  left = INF
  right = -INF
  for i in [-1,0,1]:
    left = min(left, X[i][0] + i * t)
    right = max(right, X[i][1] + i * t)
  return right - left

def area(t):
  if t < 0:
    return INF
  return calc_width(t, X) * calc_width(t, Y)

xopt = fmin(area, x0 = 10**8, ftol = 10**-9, disp = False)
answer = area(xopt[0])
print(answer)

Solution (Python):
from scipy.optimize import fmin
N = int(input())

INF = 10 ** 18
fixed_x, R, L = [], [], []
fixed_y, U, D = [], [], []

def update(fixed, li, x, y):
  li.append(x)
  fixed.append(y)
  
for _ in range(N):
  x,y,d = input().split()
  x,y = int(x), int(y)
  if d in ['L', 'R']:
    update(fixed_y, eval(d), x, y)
  else:
    update(fixed_x, eval(d), y, x)

for li in ['fixed_x', 'L', 'R', 'fixed_y', 'D', 'U']:
  exec('{0} = [min({0} + [INF]), max({0} + [-INF])]'.format(li))

def calc_x(t, fixed, dec, inc):
  left = INF
  right = -INF
  for li, speed in [(fixed, 0), (dec, -1), (inc, 1)]:
    left = min(left, li[0] + speed * t)
    right = max(right, li[1] + speed * t)
  return right - left

def area(t):
  if t < 0:
    return INF
  return calc_x(t, fixed_x, L, R) * calc_x(t, fixed_y, D, U)

xopt = fmin(area, x0 = 10**8, ftol = 10**-9, disp = False)
answer = area(xopt[0])
print(answer)

Solution (Python):
from scipy.optimize import fmin
N = int(input())

INF = 10 ** 18
fixed_x, R, L = [], [], []
fixed_y, U, D = [], [], []

def update(fixed, li, x, y):
  li.append(x)
  fixed.append(y)
  
for _ in range(N):
  x,y,d = input().split()
  x,y = int(x), int(y)
  if d == 'L':
    update(fixed_y, L, x, y)
  elif d == 'R':
    update(fixed_y, R, x, y)
  elif d == 'U':
    update(fixed_x, U, y, x)
  else:
    update(fixed_x, D, y, x)

for li in ['fixed_x', 'L', 'R', 'fixed_y', 'D', 'U']:
  exec('{0} = [min({0} + [INF]), max({0} + [-INF])]'.format(li))

def calc_x(t, fixed, dec, inc):
  left = INF
  right = -INF
  for li, speed in [(fixed, 0), (dec, -1), (inc, 1)]:
    left = min(left, li[0] + speed * t)
    right = max(right, li[1] + speed * t)
  return right - left

def area(t):
  if t < 0:
    return INF
  return calc_x(t, fixed_x, L, R) * calc_x(t, fixed_y, D, U)

xopt = fmin(area, x0 = 10**8, ftol = 10**-9, disp = False)
answer = area(xopt[0])
print(answer)

Solution (Python):
from scipy.optimize import fmin
N = int(input())

INF = 10 ** 18

fixed_x = [INF, -INF]
R = [INF, -INF]
L = [INF, -INF]

fixed_y = [INF, -INF]
U = [INF, -INF]
D = [INF, -INF]

def update(fixed, li, x, y):
  li[0], li[1] = min(li[0], x), max(li[1], x)
  fixed[0], fixed[1] = min(fixed[0], y), max(fixed[1], y)
  
for _ in range(N):
  x,y,d = input().split()
  x,y = int(x), int(y)
  if d == 'L':
    update(fixed_y, L, x, y)
  elif d == 'R':
    update(fixed_y, R, x, y)
  elif d == 'U':
    update(fixed_x, U, y, x)
  else:
    update(fixed_x, D, y, x)

def calc_x(t, fixed, dec, inc):
  left = INF
  right = -INF
  for li, speed in [(fixed, 0), (dec, -1), (inc, 1)]:
    left = min(left, li[0] + speed * t)
    right = max(right, li[1] + speed * t)
  return right - left

def area(t):
  if t < 0:
    return INF
  return calc_x(t, fixed_x, L, R) * calc_x(t, fixed_y, D, U)

xopt = fmin(area, x0 = 10**8, ftol = 10**-9, disp = False)
answer = area(xopt[0])
print(answer)

Solution (Python):



import sys
n = int(input())
inf = float("inf")
xmin = [inf, inf, inf] 
xmax = [-inf, -inf, -inf]
ymin = [inf, inf, inf]
ymax = [-inf, -inf, -inf]

for _ in range(n):
    x,y,d = [i for i in input().split()]
    x=int(x); y=int(y)
    if d=="U": ud = 2; lr = 1
    if d=="D": ud = 0; lr = 1
    if d=="L": ud = 1; lr = 0
    if d=="R": ud = 1; lr = 2
    xmin[lr] = min(xmin[lr],x)
    xmax[lr] = max(xmax[lr],x)
    ymin[ud] = min(ymin[ud],y)
    ymax[ud] = max(ymax[ud],y)

def lpos(t):
    return min([(v-1)*t + i for v,i in enumerate(xmin)])
def rpos(t):
    return max([(v-1)*t + i for v,i in enumerate(xmax)])
def dpos(t):
    return min([(v-1)*t + i for v,i in enumerate(ymin)])
def upos(t):
    return max([(v-1)*t + i for v,i in enumerate(ymax)])


s = {0}
for i in range(3):
    for j in range(i+1,3):
        t = (xmin[j]-xmin[i])/(i-j)
        if t > 0 and t != inf and t!= -inf: s.add(t)
        t = (xmax[j]-xmax[i])/(i-j)
        if 0 < t and t != inf and t!= -inf: s.add(t)
        t = (ymin[j]-ymin[i])/(i-j)
        if 0 < t and t != inf and t!= -inf: s.add(t)
        t = (ymax[j]-ymax[i])/(i-j)
        if 0 < t and t != inf and t!= -inf: s.add(t)
        

ans = 10**18
for t in s:
    area = (rpos(t)-lpos(t))*(upos(t)-dpos(t))
    if area < ans: ans = area

print(ans)

Solution (Python):
import itertools
N = int(input())
LX, LY = [], []
RX, RY = [], []
DX, DY = [], []
UX, UY = [], []

for _ in range(N):
  x,y,d = input().split()
  x,y = int(x), int(y)
  if d == 'L':
    LX.append(x)
    LY.append(y)
  elif d == 'R':
    RX.append(x)
    RY.append(y)
  elif d == 'U':
    UX.append(x)
    UY.append(y)
  else:
    DX.append(x)
    DY.append(y)

INF = 10**18
fixed_x = [min(UX + DX + [INF]), max(UX + DX + [-INF])]
fixed_y = [min(LY + RY + [INF]), max(LY + RY + [-INF])]

R_x = [min(RX + [INF]), max(RX + [-INF])]
L_x = [min(LX + [INF]), max(LX + [-INF])]
U_y = [min(UY + [INF]), max(UY + [-INF])]
D_y = [min(DY + [INF]), max(DY + [-INF])]

def calc_x(t):
  
  right = fixed_x[1]
  left = fixed_x[0]
  for x in [R_x[1]+t, L_x[1]-t]:
    if right < x:
      right = x
  for x in [R_x[0]+t, L_x[0]-t]:
    if left > x:
      left = x
  return right - left

def calc_y(t):
  
  right = fixed_y[1]
  left = fixed_y[0]
  for y in [U_y[1]+t, D_y[1]-t]:
    if right < y:
      right = y
  for y in [U_y[0]+t, D_y[0]-t]:
    if left > y:
      left = y
  return right - left

def area(t):
  if t < 0:
    return INF
  return calc_x(t) * calc_y(t)

from scipy.optimize import fmin
xopt = fmin(area, x0 = 10**8, ftol = 10**-9, disp = False)
answer = area(xopt[0])
print(answer)

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

x_list = [0]*N
y_list = [0]*N
d_list = ["A"]*N

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


def _calc_tv(v_keep, v_down, v_up):

    v_0 = min([v_keep, v_down, v_up])

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

    return t_1, t_2, v_0, v_c


def calc_tv(v_keep, v_down, v_up, reverse=False):

    if reverse:
        t_1, t_2, v_0, v_c = _calc_tv(-v_keep, -v_up, -v_down)
        return t_1, t_2, -v_0, -v_c

    else:
        return _calc_tv(v_keep, v_down, v_up)



x_sub = [x_list[i] for i in range(N) if d_list[i] in ["D", "U"]]
if len(x_sub) > 0:
    x_min_du = min(x_sub)
    x_max_du = max(x_sub)
else:
    x_min_du = 10**10
    x_max_du = -10**10
x_sub = [x_list[i] for i in range(N) if d_list[i] == "L"]
if len(x_sub) > 0:
    x_min_l = min(x_sub)
    x_max_l = max(x_sub)
else:
    x_min_l = 10**10
    x_max_l = -10**10
x_sub = [x_list[i] for i in range(N) if d_list[i] == "R"]
if len(x_sub) > 0:
    x_min_r = min(x_sub)
    x_max_r = max(x_sub)
else:
    x_min_r = 10**10
    x_max_r = -10**10

t_x_min_1, t_x_min_2, v_x_min_0, v_x_min_1 = calc_tv(x_min_du, x_min_l, x_min_r, reverse=False)
t_x_max_1, t_x_max_2, v_x_max_0, v_x_max_1 = calc_tv(x_max_du, x_max_l, x_max_r, reverse=True)


y_sub = [y_list[i] for i in range(N) if d_list[i] in ["L", "R"]]
if len(y_sub) > 0:
    y_min_lr = min(y_sub)
    y_max_lr = max(y_sub)
else:
    y_min_lr = 10**10
    y_max_lr = -10**10
y_sub = [y_list[i] for i in range(N) if d_list[i] == "D"]
if len(y_sub) > 0:
    y_min_d = min(y_sub)
    y_max_d = max(y_sub)
else:
    y_min_d = 10**10
    y_max_d = -10**10
y_sub = [y_list[i] for i in range(N) if d_list[i] == "U"]
if len(y_sub) > 0:
    y_min_u = min(y_sub)
    y_max_u = max(y_sub)
else:
    y_min_u = 10**10
    y_max_u = -10**10

t_y_min_1, t_y_min_2, v_y_min_0, v_y_min_1 = calc_tv(y_min_lr, y_min_d, y_min_u, reverse=False)
t_y_max_1, t_y_max_2, v_y_max_0, v_y_max_1 = calc_tv(y_max_lr, y_max_d, y_max_u, reverse=True)


def calc_v(t, v_type="x_min"):

    type_ind = ["x_min", "x_max", "y_min", "y_max"].index(v_type)

    t_1 = [t_x_min_1, t_x_max_1, t_y_min_1, t_y_max_1][type_ind]
    t_2 = [t_x_min_2, t_x_max_2, t_y_min_2, t_y_max_2][type_ind]
    v_0 = [v_x_min_0, v_x_max_0, v_y_min_0, v_y_max_0][type_ind]
    v_1 = [v_x_min_1, v_x_max_1, v_y_min_1, v_y_max_1][type_ind]
    c = [1, -1, 1, -1][type_ind]

    if t < t_1:
        return v_0 + c * t
    elif t < t_2:
        return v_1
    else:
        return v_1 - c * (t - t_2)


def calc_s(t):
    return (calc_v(t, "x_max") - calc_v(t, "x_min")) * (calc_v(t, "y_max") - calc_v(t, "y_min"))


t_list = [0]
t_list = t_list + [t_x_min_1, t_x_min_2]
t_list = t_list + [t_x_max_1, t_x_max_2]
t_list = t_list + [t_y_min_1, t_y_min_2]
t_list = t_list + [t_y_max_1, t_y_max_2]

res = min([calc_s(t) for t in t_list])
print(res)

Solution (Python):
N = int(input())
Xmi, Xma, Ymi, Yma, DYmi, DYma, UYmi, UYma, RXmi, RXma, LXmi, LXma = [(10**10), -(10**10)] * 6
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    
    if d == "R":
        RXmi = min(RXmi, x)
        RXma = max(RXma, x)
    elif d == "L":
        LXmi = min(LXmi, x)
        LXma = max(LXma, x)
    else:
        Xmi = min(Xmi, x)
        Xma = max(Xma, x)
        
    if d == "U":
        UYmi = min(UYmi, y)
        UYma = max(UYma, y)
    elif d == "D":
        DYmi = min(DYmi, y)
        DYma = max(DYma, y)
    else:
        Ymi = min(Ymi, y)
        Yma = max(Yma, y)

def calc(t):
    xmi = min(RXmi+t, LXmi-t, Xmi)
    xma = max(RXma+t, LXma-t, Xma)
    ymi = min(UYmi+t, DYmi-t, Ymi)
    yma = max(UYma+t, DYma-t, Yma)
    return max(yma-ymi, 0)*max(xma-xmi, 0)
    
def di(t):
    a = 1
    return calc(t+a) - calc(t-a)
def dii(t):
    a = 0.0000001
    return calc(t+a) - calc(t-a)

l = 0
r = 10**10
for _ in range(100):
    m = (l+r)//2
    if di(m) > 0:
        r = m
    else:
        l = m
for _ in range(100):
    m = (l+r)/2
    if dii(m) > 0:
        r = m
    else:
        l = m
print(calc(m))

Solution (Python):
from decimal import *
getcontext().prec = 100
N = int(input())
Xmi, Xma, Ymi, Yma, DYmi, DYma, UYmi, UYma, RXmi, RXma, LXmi, LXma = [(10**10), -(10**10)] * 6
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    
    if d == "R":
        RXmi = min(RXmi, x)
        RXma = max(RXma, x)
    elif d == "L":
        LXmi = min(LXmi, x)
        LXma = max(LXma, x)
    else:
        Xmi = min(Xmi, x)
        Xma = max(Xma, x)
        
    if d == "U":
        UYmi = min(UYmi, y)
        UYma = max(UYma, y)
    elif d == "D":
        DYmi = min(DYmi, y)
        DYma = max(DYma, y)
    else:
        Ymi = min(Ymi, y)
        Yma = max(Yma, y)

def calc(t):
    xmi = min(RXmi+t, LXmi-t, Xmi)
    xma = max(RXma+t, LXma-t, Xma)
    ymi = min(UYmi+t, DYmi-t, Ymi)
    yma = max(UYma+t, DYma-t, Yma)
    return max(yma-ymi, 0)*max(xma-xmi, 0)
    
def dii(t):
    a = Decimal("0.00000001")
    return calc(t+a) - calc(t-a)

l = Decimal("0")
r = Decimal("10000000000")
for _ in range(500):
    m = (l+r)/2
    if dii(m) > 0:
        r = m
    else:
        l = m
print(calc(m))

Solution (Python):
INF = float('inf')
N = int(input())
d = {'R':[[],[]],'L':[[],[]],'U':[[],[]],'D':[[],[]]}
for i in range(N):
    x,y,f = input().split()
    x = int(x)
    y = int(y)
    d[f][0].append(x)
    d[f][1].append(y)

Ts = []

xM = max(max(d['U'][0]+[-INF]),max(d['D'][0]+[-INF]))
xMr = max(d['R'][0]+[-INF])
xMl = max(d['L'][0]+[-INF])

def xmax(T):
    return max(xM,xMr+T,xMl-T)

Ts += [max(0,xMl-xM),max(0,xM-xMr),max(0,(xMl-xMr)/2)]

xm = min(min(d['U'][0]+[INF]),min(d['D'][0]+[INF]))
xmr = min(d['R'][0]+[INF])
xml = min(d['L'][0]+[INF])

def xmin(T):
    return min(xm,xmr+T,xml-T)

Ts += [max(0,xml-xm),max(0,xm-xmr),max(0,(xml-xmr)/2)]

yM = max(max(d['R'][1]+[-INF]),max(d['L'][1]+[-INF]))
yMu = max(d['U'][1]+[-INF])
yMd = max(d['D'][1]+[-INF])

def ymax(T):
    return max(yM,yMu+T,yMd-T)

Ts += [max(0,yMd-yM),max(0,yM-yMu),max(0,(yMd-yMu)/2)]

ym = min(min(d['R'][1]+[INF]),min(d['L'][1]+[INF]))
ymu = min(d['U'][1]+[INF])
ymd = min(d['D'][1]+[INF])

def ymin(T):
    return min(ym,ymu+T,ymd-T)

Ts += [max(0,ymd-ym),max(0,ym-ymu),max(0,(ymd-ymu)/2)]

ans = INF

for T in Ts:
    ans = min(ans,(xmax(T)-xmin(T))*(ymax(T)-ymin(T)))

print(ans)

Solution (Python):
import sys

from math import floor


def check(t):
    maxx, minx, maxy, miny = ud_maxx, ud_minx, lr_maxy, lr_miny
    for x, y in dots['R']:
        maxx = max(maxx, x + t)
        minx = min(minx, x + t)
    for x, y in dots['L']:
        maxx = max(maxx, x - t)
        minx = min(minx, x - t)
    for x, y in dots['U']:
        maxy = max(maxy, y + t)
        miny = min(miny, y + t)
    for x, y in dots['D']:
        maxy = max(maxy, y - t)
        miny = min(miny, y - t)
    return (maxx - minx) * (maxy - miny)


n = int(input())
dots = {'R': set(), 'L': set(), 'U': set(), 'D': set()}
lr_maxy, lr_miny, ud_maxx, ud_minx = -1e9, 1e9, -1e9, 1e9
for line in sys.stdin:
    x, y, d = line.rstrip().split()
    x, y = int(x), int(y)
    dots[d].add((x, y))
    if d in 'LR':
        lr_maxy = max(lr_maxy, y)
        lr_miny = min(lr_miny, y)
    else:
        ud_maxx = max(ud_maxx, x)
        ud_minx = min(ud_minx, x)

l = 0.0
r = float(1 << 30)

while l < r - 1:
    m1 = l + floor((r - l) / 3 * 2) / 2
    m2 = l + floor((r - l) / 3 * 4) / 2
    c1 = check(m1)
    c2 = check(m2)
    
    if c1 >= c2:
        l = m1
    else:
        r = m2

ans = float(1e17)
l = max(0.0, floor(l * 2 - 16) / 2)
while l <= r + 8:
    ans = min(ans, check(l))
    l += 0.5
print(ans)