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):
N=int(input())
import sys
input=sys.stdin.readline
inf=10**20
dd = {
        'R':[-inf]*3,
        'L':[inf]*3,
        'U':[-inf]*3,
        'D':[inf]*3,
        }
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    if d == 'R':
        dd['R'][0] = max(x, dd['R'][0])
        dd['L'][1] = min(x, dd['L'][1])
        dd['U'][2] = max(y, dd['U'][2])
        dd['D'][2] = min(y, dd['D'][2])
    elif d == 'L':
        dd['L'][0] = min(x, dd['L'][0])
        dd['R'][1] = max(x, dd['R'][1])
        dd['U'][2] = max(y, dd['U'][2])
        dd['D'][2] = min(y, dd['D'][2])
    elif d == 'U':
        dd['R'][2] = max(x, dd['R'][2])
        dd['L'][2] = min(x, dd['L'][2])
        dd['U'][0] = max(y, dd['U'][0])
        dd['D'][1] = min(y, dd['D'][1])
    elif d == 'D':
        dd['R'][2] = max(x, dd['R'][2])
        dd['L'][2] = min(x, dd['L'][2])
        dd['U'][1] = max(y, dd['U'][1])
        dd['D'][0] = min(y, dd['D'][0])

tls = []
for d in "RLUD":
    m = -1 if d in 'RU' else 1
    t1 = -m*(dd[d][1] - dd[d][2])
    t2 = -m*(dd[d][2] - dd[d][0])
    t3 = m*float(dd[d][0] - dd[d][1])/2
    
    if t1 < t3 and t3 < t2:
        if t1 > 0:
            tls.append((0, m, dd[d][1], d))
        if t2 > 0:
            tls.append((max(0, t1), 0, dd[d][2], d))
        tls.append((max(0, t2), -m, dd[d][0], d))
    else:
        if t3 > 0:
            tls.append((0, m, dd[d][1], d))
        tls.append((max(0, t3), -m, dd[d][0], d))

tls.sort()
btl = 0
r = 10**20
for t, a, b, d in tls:
    if btl > 10**10:
        btl = inf
        break
    if t != btl:
        a1=(dd['R'][0] - dd['L'][0])
        a2=(dd['U'][0] - dd['D'][0])
        b1=(dd['R'][1] - dd['L'][1])
        b2=(dd['U'][1] - dd['D'][1])
        r = min(r, (a1*t+b1)*(a2*t+b2))
        r = min(r, (a1*btl+b1)*(a2*btl+b2))
        
    dd[d] = (a, b)
    btl = t
if btl < inf:
    t = inf
    a1=(dd['R'][0] - dd['L'][0])
    a2=(dd['U'][0] - dd['D'][0])
    b1=(dd['R'][1] - dd['L'][1])
    b2=(dd['U'][1] - dd['D'][1])
    r = min(r, (a1*t+b1)*(a2*t+b2))
    r = min(r, (a1*btl+b1)*(a2*btl+b2))


print(r)

Solution (Python):
import itertools

def enum(a):
    t = [0]
    for a1, a2 in itertools.combinations(a, 2):
        t.append(a1[0]-a2[0])
        t.append(a2[0]-a1[0])
        t.append((a1[0]-a2[0])/2)
        t.append((a2[0]-a1[0])/2)
    return t

def calcWidth(l, t):
    x_min = x_max = l[0][0] + l[0][1] * t
    for item in l:
        x_min = min(x_min, item[0] + item[1] * t)
        x_max = max(x_max, item[0] + item[1] * t)
    return x_max - x_min

def calc(x_trip, y_trip, t):
    if t < 0:
        return calcWidth(x_trip, 0) * calcWidth(y_trip, 0)
    return calcWidth(x_trip, t) * calcWidth(y_trip, t)

n = int(input())
x_r, x_n, x_l = [], [], []
y_u, y_n, y_d = [], [], []
for _ in range(n):
    x, y, d = input().strip().split()
    x, y = int(x), int(y)
    if d == "R":
        x_r.append(x)
    elif d == "L":
        x_l.append(x)
    else:
        x_n.append(x)

    if d == "U":
        y_u.append(y)
    elif d == "D":
        y_d.append(y)
    else:
        y_n.append(y)

x_r.sort()
x_n.sort()
x_l.sort()
y_u.sort()
y_n.sort()
y_d.sort()

def ht(x, d):
    if len(x) > 0:
        return [(x[0], d), (x[-1], d)]
    return []
x_list = ht(x_r, 1) + ht(x_n, 0) + ht(x_l, -1)
y_list = ht(y_u, 1) + ht(y_n, 0) + ht(y_d, -1)
t = enum(x_list + y_list)

ans = calc(x_list, y_list, 0)
for t1 in t:
    if t1 < 0:
        continue
    wx = calcWidth(x_list, t1)
    wy = calcWidth(y_list, t1)
    ans = min(ans, calc(x_list, y_list, t1))
    ans = min(ans, calc(x_list, y_list, t1 + (wx-wy)/2))
    ans = min(ans, calc(x_list, y_list, t1 + (wy-wx)/2))
    ans = min(ans, calc(x_list, y_list, t1 + (wx*2-wy)/4))
    ans = min(ans, calc(x_list, y_list, t1 + (wx-wy*2)/4))
    ans = min(ans, calc(x_list, y_list, t1 + (wy*2-wx)/4))
    ans = min(ans, calc(x_list, y_list, t1 + (wy-wx*2)/4))
    ans = min(ans, calc(x_list, y_list, t1 + (wx*2-wy*2)/8))
    ans = min(ans, calc(x_list, y_list, t1 + (wy*2-wx*2)/8))
print(ans)

Solution (Python):
import itertools as ite
import math
import random

INF = 10 ** 18
MOD = 10 ** 9 + 7

dx_ = [-1, 1, 0, 0]
dy_ = [0, 0, -1, 1]

m = {"L" : 0, "R" : 1, "D" : 2, "U" : 3}

N = input()
ls = []
ts = [0]

x1 = x2 = x3 = y1 = y2 = y3 = -INF

for loop in range(N):
    x, y, d = raw_input().split()
    x, y = int(x), int(y)
    d = m[d]
    ls += [(x, y, d)]
    if d == 0:
        x1 = max(x1, x)
        y2 = max(y2, y)
    if d == 1:
        x3 = max(x3, x)
        y2 = max(y2, y)
    if d == 2:
        x2 = max(x2, x)
        y1 = max(y1, y)
    if d == 3:
        x2 = max(x2, x)
        y3 = max(y3, y)
ts += [x1 - x2, x2 - x3, (x1 - x3) / 2.0]
ts += [y1 - y2, y2 - y3, (y1 - y3) / 2.0]

x1 = x2 = x3 = y1 = y2 = y3 = -INF

for x, y, d in ls:
    x, y = -x, -y
    d = d / 2 * 2 + (d % 2 == 0)
    if d == 0:
        x1 = max(x1, x)
        y2 = max(y2, y)
    if d == 1:
        x3 = max(x3, x)
        y2 = max(y2, y)
    if d == 2:
        x2 = max(x2, x)
        y1 = max(y1, y)
    if d == 3:
        x2 = max(x2, x)
        y3 = max(y3, y)
ts += [x1 - x2, x2 - x3, (x1 - x3) / 2.0]
ts += [y1 - y2, y2 - y3, (y1 - y3) / 2.0]

ans = INF

for t in ts:
    if t < 0 or t > 10 ** 10:
        continue
    x1 = y1 = INF
    x2 = y2 = -INF
    for x, y, d in ls:
        dx, dy = dx_[d], dy_[d]
        X = x + dx * t
        Y = y + dy * t
        x1 = min(x1, X)
        x2 = max(x2, X)
        y1 = min(y1, Y)
        y2 = max(y2, Y)
    ans = min(ans, (x2 - x1) * (y2 - y1))
print "%.12f" % ans

Solution (Python):


from collections import deque, defaultdict
import itertools as ite
import sys
import math
import decimal

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()

UMaxY = DMaxY = OMaxY = -INF
UMinY = DMinY = OMinY = INF
LMaxX = RMaxX = OMaxX = -INF
LMinX = RMinX = OMinX = INF

for i in range(N):
    x, y, d = raw_input().split()
    x, y = int(x) * 2, int(y) * 2
    if d == 'U':
        UMaxY = max(UMaxY, y)
        UMinY = min(UMinY, y)
        OMaxX = max(OMaxX, x)
        OMinX = min(OMinX, x)
    if d == 'D':
        DMaxY = max(DMaxY, y)
        DMinY = min(DMinY, y)
        OMaxX = max(OMaxX, x)
        OMinX = min(OMinX, x)
    if d == 'L':
        OMaxY = max(OMaxY, y)
        OMinY = min(OMinY, y)
        LMaxX = max(LMaxX, x)
        LMinX = min(LMinX, x)
    if d == 'R':
        OMaxY = max(OMaxY, y)
        OMinY = min(OMinY, y)
        RMaxX = max(RMaxX, x)
        RMinX = min(RMinX, x)
'''
print UMaxY, DMaxY, OMaxY
print UMinY, DMinY, OMinY
print LMaxX, RMaxX, OMaxX
print LMinX, RMinX, OMinX
'''
ts = [0]
ts += [DMaxY - OMaxY, OMaxY - UMaxY, (DMaxY - UMaxY) / 2]
ts += [DMinY - OMinY, OMinY - UMinY, (DMinY - UMinY) / 2]
ts += [LMaxX - OMaxX, OMaxX - RMaxX, (LMaxX - RMaxX) / 2]
ts += [LMinX - OMinX, OMinX - RMinX, (LMinX - RMinX) / 2]

ans = 10 ** 30
for t in ts:
    if t < 0 or 10 ** 10 < t:
        continue
    maxY = max(DMaxY - t, UMaxY + t, OMaxY)
    minY = min(DMinY - t, UMinY + t, OMinY)
    maxX = max(LMaxX - t, RMaxX + t, OMaxX)
    minX = min(LMinX - t, RMinX + t, OMinX)
    ans = min(ans, (maxY - minY) * (maxX - minX))
print float(ans) / 4

Solution (Python):
N=int(input())
inf=float("inf")
data=[[inf,-inf,inf,-inf] for i in range(4)]
dic={ "U" : 0 , "D" : 1 , "R" : 2 , "L" : 3 }

for i in range(N):
    x,y,d=input().split()
    x,y=int(x),int(y)
    u=data[dic[d]]
    u[0]=min(u[0],x)
    u[1]=max(u[1],x)
    u[2]=min(u[2],y)
    u[3]=max(u[3],y)

a,b,c,d=data[0]
e,f,g,h=data[1]
i,j,k,l=data[2]
m,n,o,p=data[3]

a=min(a,e)
b=max(b,f)
k=min(k,o)
l=max(l,p)

if a==inf:
    a=-inf
    b=inf

time=[0]
time.append(a-i)
time.append(m-a)
time.append((m-i)/2)
time.append(b-j)
time.append(n-b)
time.append((n-j)/2)
time.append(k-c)
time.append(g-k)
time.append((g-c)/2)
time.append(l-d)
time.append(h-l)
time.append((h-d)/2)

ans=inf
for t in time:
    if 0<=t<=10**10:
        lst=[]
        for u in data:
            lst.append(u[:])
        lst[2][0]+=t
        lst[2][1]+=t
        lst[0][2]+=t
        lst[0][3]+=t
        lst[3][0]-=t
        lst[3][1]-=t
        lst[1][2]-=t
        lst[1][3]-=t
        
        lsls=[]
        for j in range(4):
            if j%2==0:
                m=inf
                for i in range(4):
                    m=min(m,lst[i][j])
                lsls.append(m)
            else:
                M=-inf
                for i in range(4):
                    M=max(M,lst[i][j])
                lsls.append(M)
        ans=min(ans,(lsls[1]-lsls[0])*(lsls[3]-lsls[2]))

print(ans)

Solution (Python):
inf = float('inf')
from scipy.optimize import fmin
from collections import defaultdict
dir = {'R', 'L', 'U', 'D'}
N = int(input())
dic = defaultdict(list)
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    dic[d].append((x, y))
x_max = defaultdict(lambda : -inf)
x_min = defaultdict(lambda : inf)
y_max = defaultdict(lambda : -inf)
y_min = defaultdict(lambda : inf)
for d in dir:
    if dic[d]:
        dic[d].sort()
        x_max[d] = dic[d][-1][0]
        x_min[d] = dic[d][0][0]
        dic[d].sort(key = lambda x:x[1])
        y_max[d] = dic[d][-1][1]
        y_min[d] = dic[d][0][1]
def dx(t):
    return max(x_max['U'], x_max['D'], x_max['R']+t, x_max['L']-t)-min(x_min['U'], x_min['D'], x_min['R']+t, x_min['L']-t)
def dy(t):
    return max(y_max['U']+t, y_max['D']-t, y_max['R'], y_max['L'])-min(y_min['U']+t, y_min['D']-t, y_min['R'], y_min['L'])
def f(t):
    if t<0:
        return inf
    return dx(t)*dy(t)
def make_cand(s, d, i):
    return [abs(s-i), abs(d-i)/2, abs(s-d)]
cand = [0]+make_cand(max(x_max['U'], x_max['D']), x_max['R'], x_max['L'])               +make_cand(min(x_min['U'], x_min['D']), x_min['R'], x_min['L'])               +make_cand(max(y_max['R'], y_max['L']), y_max['U'], y_max['D'])               +make_cand(min(y_min['R'], y_min['L']), y_min['U'], y_min['D'])
ans = min(f(t)for t in cand)
print(ans)

Solution (Python):
inf = float('inf')
from scipy.optimize import fmin
from collections import defaultdict
dir = {'R', 'L', 'U', 'D'}
N = int(input())
dic = defaultdict(list)
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    dic[d].append((x, y))
x_max = defaultdict(lambda : -inf)
x_min = defaultdict(lambda : inf)
y_max = defaultdict(lambda : -inf)
y_min = defaultdict(lambda : inf)
for d in dir:
    if dic[d]:
        dic[d].sort()
        x_max[d] = dic[d][-1][0]
        x_min[d] = dic[d][0][0]
        dic[d].sort(key = lambda x:x[1])
        y_max[d] = dic[d][-1][1]
        y_min[d] = dic[d][0][1]
def dx(t):
    return max(x_max['U'], x_max['D'], x_max['R']+t, x_max['L']-t)-min(x_min['U'], x_min['D'], x_min['R']+t, x_min['L']-t)
def dy(t):
    return max(y_max['U']+t, y_max['D']-t, y_max['R'], y_max['L'])-min(y_min['U']+t, y_min['D']-t, y_min['R'], y_min['L'])
def f(t):
    if t<0:
        return inf
    return dx(t)*dy(t)

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=10**9
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    X=[[INF,-INF] for _ in range(3)]
    Y=[[INF,-INF] for _ in range(3)]
    for _ in range(n):
        x,y,d=input().split()
        x=int(x); y=int(y)
        if(d=='R'):
            X[2][0]=min(X[2][0],x)
            X[2][1]=max(X[2][1],x)
            Y[1][0]=min(Y[1][0],y)
            Y[1][1]=max(Y[1][1],y)
        elif(d=='L'):
            X[0][0]=min(X[0][0],x)
            X[0][1]=max(X[0][1],x)
            Y[1][0]=min(Y[1][0],y)
            Y[1][1]=max(Y[1][1],y)
        elif(d=='U'):
            X[1][0]=min(X[1][0],x)
            X[1][1]=max(X[1][1],x)
            Y[2][0]=min(Y[2][0],y)
            Y[2][1]=max(Y[2][1],y)
        elif(d=='D'):
            X[1][0]=min(X[1][0],x)
            X[1][1]=max(X[1][1],x)
            Y[0][0]=min(Y[0][0],y)
            Y[0][1]=max(Y[0][1],y)

    T=[0]
    for i in range(3):
        for j in range(i): 
            t=-(X[i][0]-X[j][0])/(i-j)
            if(t>0): T.append(t)
            t=-(X[i][1]-X[j][1])/(i-j)
            if(t>0): T.append(t)
            t=-(Y[i][0]-Y[j][0])/(i-j)
            if(t>0): T.append(t)
            t=-(Y[i][1]-Y[j][1])/(i-j)
            if(t>0): T.append(t)

    def f(t):
        x_min=min(X[0][0],X[1][0]+t,X[2][0]+2*t)
        x_max=max(X[0][1],X[1][1]+t,X[2][1]+2*t)
        y_min=min(Y[0][0],Y[1][0]+t,Y[2][0]+2*t)
        y_max=max(Y[0][1],Y[1][1]+t,Y[2][1]+2*t)
        return (x_max-x_min)*(y_max-y_min)

    ans=float("inf")
    for t in T:
        ans=min(ans,f(t))
    print(ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=10**9
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class D(object):
    def __init__(self):
        self.L=[INF]*3
        self.R=[-INF]*3

    def add(self,x,v):
        v+=1
        self.L[v]=min(self.L[v],x)
        self.R[v]=max(self.R[v],x)

    def get(self,t):
        l=INF; r=-INF
        L=self.L; R=self.R
        for i in range(3):
            l=min(L[i]+i*t,l)
            r=max(R[i]+i*t,r)
        return r-l

    def event(self):
        L=self.L; R=self.R
        res=[]
        for i in range(3):
            for j in range(i): 
                t=(L[j]-L[i])/(i-j)
                if(t>0): res.append(t)
        for i in range(3):
            for j in range(i): 
                t=(R[j]-R[i])/(i-j)
                if(t>0): res.append(t)
        return res

def resolve():
    n=int(input())
    xd=D()
    yd=D()
    for i in range(n):
        x,y,d=input().split()
        x=int(x); y=int(y)
        if(d=='R'):
            xd.add(x,1)
            yd.add(y,0)
        elif(d=='L'):
            xd.add(x,-1)
            yd.add(y,0)
        elif(d=='U'):
            xd.add(x,0)
            yd.add(y,1)
        elif(d=='D'):
            xd.add(x,0)
            yd.add(y,-1)
    T=[0]+xd.event()+yd.event()
    ans=float("inf")
    for t in T:
        ans=min(ans,xd.get(t)*yd.get(t))
    print(ans)
resolve()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF = 10**18

data = {x:[-INF,INF,-INF,INF]for x in 'RLUD'}

N = int(readline())
XYD = read().split()
X = (int(x) for x in XYD[::3])
Y = (int(x) for x in XYD[1::3])
D = (x.decode('utf-8') for x in XYD[2::3])

for x,y,d in zip(X,Y,D):
    if data[d][0] < x: data[d][0] = x
    if data[d][1] > x: data[d][1] = x
    if data[d][2] < y: data[d][2] = y
    if data[d][3] > y: data[d][3] = y

X = []
Y = []

X += [(data['L'][0],-1), (data['L'][1],-1)]
X += [(data['R'][0],1), (data['R'][1],1)]
X += [(data['U'][0],0), (data['U'][1],0)]
X += [(data['D'][0],0), (data['D'][1],0)]

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

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

T = []
for (x,dx),(y,dy) in itertools.combinations(X,2):
    if dx == dy: continue
    
    T.append((x-y)/(dy-dx))
for (x,dx),(y,dy) in itertools.combinations(Y,2):
    if dx == dy: continue
    
    T.append((x-y)/(dy-dx))

T = set([0] + [t for t in T if t > 0])

def F(t):
    xs = [x+t*speed for x,speed in X]
    ys = [x+t*speed for x,speed in Y]
    dx = max(xs) - min(xs)
    dy = max(ys) - min(ys)
    return dx*dy

answer = min(F(t) for t in T)
print(answer)

Solution (Python):
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN

def want(n):

    xmax = float("-inf")
    xmin = float("inf")
    ymax = float("-inf")
    ymin = float("inf")

    if L:
        xmax = max(xmax,L_R - n)
        xmin = min(xmin,L_L - n)
        ymax = max(ymax,LR_U)
        ymin = min(ymin,LR_D)

    if R:
        xmax = max(xmax,R_R + n)
        xmin = min(xmin,R_L + n)
        ymax = max(ymax,LR_U)
        ymin = min(ymin,LR_D)

    if D:
        xmax = max(xmax,UD_R)
        xmin = min(xmin,UD_L)
        ymax = max(ymax,D_U - n)
        ymin = min(ymin,D_D - n)

    if U:
        xmax = max(xmax,UD_R)
        xmin = min(xmin,UD_L)
        ymax = max(ymax,U_U + n)
        ymin = min(ymin,U_D + n)

    
    return abs(xmax - xmin) * abs(ymax - ymin)

def my_round(val, digit=0):
    p = 10 ** digit
    return (val * p * 2 + 1) // 2 / p


N = int(input())

UD_L = float("inf")
UD_R = float("-inf")
L_L = float("inf")
L_R = float("-inf")
R_L = float("inf")
R_R = float("-inf")

LR_D = float("inf")
LR_U = float("-inf")
D_D = float("inf")
D_U = float("-inf")
U_D = float("inf")
U_U = float("-inf")

U = False
D = False
L = False
R = False

for i in range(N):

    x,y,d = input().split()

    x = int(x)
    y = int(y)

    if d == "L" or d == "R":
        LR_D = min(LR_D,y)
        LR_U = max(LR_U,y)

        if d == "L":

            L_L = min(L_L,x)
            L_R = max(L_R,x)
            L = True

        else: 

            R_L = min(R_L,x)
            R_R = max(R_R,x)
            R = True

    if d == "D" or d == "U":

        UD_L = min(UD_L,x)
        UD_R = max(UD_R,x)

        if d == "D":

            D_D = min(D_D,y)
            D_U = max(D_U,y)
            D = True

        else: 

            U_D = min(U_D,y)
            U_U = max(U_U,y)
            U = True

t0 = 0
t3 = 2 * 10 ** 8
last = float("inf")
ans = 1000000000000000000000

while abs(last - ans) > 10 ** (-100):

    t1 = Decimal((t0 * 2 + t3 * 1)) / Decimal(3)
    t2 = Decimal((t0 * 1 + t3 * 2)) / Decimal(3)

    

    last = ans
    
    if want(t1) <= want(t2):
        ans = want(t1)
        t3 = t2

    else:
        ans = want(t2)
        t0 = t1

    

if ans <= 10 ** (-9):
    ans = 0
print ('{:.20g}'.format(ans))

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

INF = 10**30
n = int(input())
p = [input().split() for _ in range(n)]

"""
[0]: max or min / for
[1]: max or min / against
[2]: max or min / fixed
"""

r = [-INF, -INF, -INF]
l = [INF, INF, INF]
u = [-INF, -INF, -INF]
d = [INF, INF, INF]

for x, y, t in p:
	x, y = int(x), int(y)
	if t == "R":
		r[0] = max(r[0], x)
		l[1] = min(l[1], x)
		u[2] = max(u[2], y)
		d[2] = min(d[2], y)
	elif t == "L":
		r[1] = max(r[1], x)
		l[0] = min(l[0], x)
		u[2] = max(u[2], y)
		d[2] = min(d[2], y)
	elif t == "U":
		r[2] = max(r[2], x)
		l[2] = min(l[2], x)
		u[0] = max(u[0], y)
		d[1] = min(d[1], y)
	else:
		r[2] = max(r[2], x)
		l[2] = min(l[2], x)
		u[1] = max(u[1], y)
		d[0] = min(d[0], y)






timings = set([0])

if r[0] <= r[1] <= r[2]:
	timings.add(abs(r[2]-r[0]))
elif r[0] <= r[2] <= r[1]:
	timings.add(abs(r[1]-r[0])/2)
	timings.add(abs(r[2]-r[0]))
	timings.add(abs(r[1]-r[2]))
elif r[1] <= r[0] <= r[2]:
	timings.add(abs(r[2]-r[0]))
elif r[2] <= r[0] <= r[1]:
	timings.add(abs(r[1]-r[0])/2)

if l[0] >= l[1] >= l[2]:
	timings.add(abs(l[2]-l[0]))
elif l[0] >= l[2] >= l[1]:
	timings.add(abs(l[1]-l[0])/2)
	timings.add(abs(l[2]-l[0]))
	timings.add(abs(l[1]-l[2]))
elif l[1] >= l[0] >= l[2]:
	timings.add(abs(l[2]-l[0]))
elif l[2] >= l[0] >= l[1]:
	timings.add(abs(l[1]-l[0])/2)

if u[0] <= u[1] <= u[2]:
	timings.add(abs(u[2]-u[0]))
elif u[0] <= u[2] <= u[1]:
	timings.add(abs(u[1]-u[0])/2)
	timings.add(abs(u[2]-u[0]))
	timings.add(abs(u[1]-u[2]))
elif u[1] <= u[0] <= u[2]:
	timings.add(abs(u[2]-u[0]))
elif u[2] <= u[0] <= u[1]:
	timings.add(abs(u[1]-u[0])/2)

if d[0] >= d[1] >= d[2]:
	timings.add(abs(d[2]-d[0]))
elif d[0] >= d[2] >= d[1]:
	timings.add(abs(d[1]-d[0])/2)
	timings.add(abs(d[2]-d[0]))
	timings.add(abs(d[1]-d[2]))
elif d[1] >= d[0] >= d[2]:
	timings.add(abs(d[2]-d[0]))
elif d[2] >= d[0] >= d[1]:
	timings.add(abs(d[1]-d[0])/2)


ans = 10**30
for t in timings:
	if t > 10**10:
		continue
	R, L, U, D = -INF, INF, -INF, INF
	for x, y, di in p:
		if di == "R":
			x, y = int(x)+t, int(y)
		elif di == "L":
			x, y = int(x)-t, int(y)
		elif di == "U":
			x, y = int(x), int(y)+t
		else:
			x, y = int(x), int(y)-t

		R = max(R, x)
		L = min(L, x)
		U = max(U, y)
		D = min(D, y)

	ans = min(ans, (R-L)*(U-D))

print(ans)

Solution (Python):
N = int(input())
M = {'R': [], 'L':[], 'U': [], 'D': [], 'X': [], 'Y': []}
for _ in range(N):
  x, y, d = input().split()
  if d in ['R', 'L']:
    M[d].append(int(x))
    M['Y'].append(int(y))
  else:
    M['X'].append(int(x))
    M[d].append(int(y))
for d in 'RLDUXY':
  M[d] = sorted(M[d])
T = [0] * 13
T[0] = M['X'][0] - M['R'][0] if M['X'] and M['R'] else -1
T[1] = M['L'][0] - M['X'][0] if M['X'] and M['L'] else -1
T[2] = (M['L'][0] - M['R'][0]) / 2 if M['L'] and M['R'] else -1
T[3] = M['X'][-1] - M['R'][-1] if M['X'] and M['R'] else -1
T[4] = M['L'][-1] - M['X'][-1] if M['X'] and M['L'] else -1
T[5] = (M['L'][-1] - M['R'][-1]) / 2 if M['L'] and M['R'] else -1
T[6] = M['Y'][-1] - M['U'][-1] if M['Y'] and M['U'] else -1
T[7] = M['D'][-1] - M['Y'][-1] if M['Y'] and M['D'] else -1
T[8] = (M['D'][-1] - M['U'][-1]) / 2 if M['D'] and M['U'] else -1
T[9] = M['Y'][0] - M['U'][0] if M['Y'] and M['U'] else -1
T[10] = M['D'][0] - M['Y'][0] if M['Y'] and M['D'] else -1
T[11] = (M['D'][0] - M['U'][0]) / 2 if M['D'] and M['U'] else -1
Rect = [-1] * 13
for i, t in enumerate(T):
  if t < 0:
    continue
  R = []
  L = []
  U = []
  D = []
  if M['R']:
    R.append(M['R'][-1] + t)
    L.append(M['R'][0] + t)
  if M['L']:
    R.append(M['L'][-1] - t)
    L.append(M['L'][0] - t)
  if M['U']:
    U.append(M['U'][-1] + t)
    D.append(M['U'][0] + t)
  if M['D']:
    U.append(M['D'][-1] - t)
    D.append(M['D'][0] - t)
  if M['X']:
    R.append(M['X'][-1])
    L.append(M['X'][0])
  if M['Y']:
    U.append(M['Y'][-1])
    D.append(M['Y'][0])
  Rect[i] = (max(R) - min(L)) * (max(U) - min(D))
print(min([r for r in Rect if r >= 0]))

Solution (Python):
import numpy as np
from scipy.optimize import fmin

INF = 10**18

mapping = {
    "R": (1, 0),
    "L": (-1, 0),
    "U": (0, 1),
    "D": (0, -1)
}

def f(x, vx, t):
    if t < 0:
        return INF
    nx = x + vx * t
    return nx.max() - nx.min()

def solve(n, x, y, d):
    x = np.asarray(x, dtype=np.float)
    y = np.asarray(y, dtype=np.float)
    vx = np.zeros(n, dtype=np.float)
    vy = np.zeros(n, dtype=np.float)
    for i in range(n):
        vx[i], vy[i] = mapping[d[i]]
    h = lambda t: f(y, vy, t) * f(x, vx, t)
    t = fmin(h, x0=10**8, ftol=1e-9, disp=False)[0]
    return h(t)

n = int(input())
x, y, d = [-1]*n, [-1]*n, [-1]*n
for i in range(n):
    x[i], y[i], d[i] = input().split()
    x[i] = int(x[i])
    y[i] = int(y[i])
print(solve(n, x, y, d))

Solution (Python):
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

BIG = 10**18
n = inn()
rx = []
udx = []
lx = []
uy =[]
rly = []
dy = []
for i in range(n):
    x,y,d = input().split()
    x = int(x)
    y = int(y)
    if d=='R':
        rx.append(x)
        rly.append(y)
    elif d=='L':
        lx.append(x)
        rly.append(y)
    elif d=='U':
        udx.append(x)
        uy.append(y)
    elif d=='D':
        udx.append(x)
        dy.append(y)

nor = (len(rx)==0)
nol = (len(lx)==0)
nou = (len(uy)==0)
nod = (len(dy)==0)
noud = nou and nod
norl = nor and nol

if not nor:
    rx.sort()
    rmax  = rx[-1]
    rmin  = rx[0]
if not nol:
    lx.sort()
    lmax  = lx[-1]
    lmin  = lx[0]
if not nou:
    uy.sort()
    umax  = uy[-1]
    umin  = uy[0]
if not nod:
    dy.sort()
    dmax  = dy[-1]
    dmin  = dy[0]
if not noud:
    udx.sort()
    udmax  = udx[-1]
    udmin  = udx[0]
if not norl:
    rly.sort()
    rlmax  = rly[-1]
    rlmin  = rly[0]

ddprint(rx)
ddprint(udx)
ddprint(lx)



def foo(t):
    ddprint("foo t: {}".format(t))
    xmax = -BIG
    if not nor:
        xmax = max(xmax, rmax+t)
    if not noud:
        xmax = max(xmax, udmax)
    if not nol:
        xmax = max(xmax, lmax-t)
    xmin = BIG
    if not nor:
        xmin = min(xmin, rmin+t)
    if not noud:
        xmin = min(xmin, udmin)
    if not nol:
        xmin = min(xmin, lmin-t)

    ymax = -BIG
    if not nou:
        ymax = max(ymax, umax+t)
    if not norl:
        ymax = max(ymax, rlmax)
    if not nod:
        ymax = max(ymax, dmax-t)
    ymin = BIG
    if not nou:
        ymin = min(ymin, umin+t)
    if not norl:
        ymin = min(ymin, rlmin)
    if not nod:
        ymin = min(ymin, dmin-t)

    z = abs((xmax-xmin)*(ymax-ymin))
    ddprint("xmax {} xmin {} ymax {} ymin {} rtn {}".format(xmax,xmin,ymax,ymin,z))
    return z

ts = [0]
if not noud:
    if not nor:
        ts.append(max(0,udmax-rmax))
        ts.append(max(0,udmin-rmin))
    if not nol:
        ts.append(max(0,lmax-udmax))
        ts.append(max(0,lmin-udmin))
if not nol and not nor:
        ts.append(max(0,(lmax-rmax)/2))
        ts.append(max(0,(lmin-rmin)/2))
if not norl:
    if not nou:
        ts.append(max(0,rlmax-umax))
        ts.append(max(0,rlmin-umin))
    if not nod:
        ts.append(max(0,dmax-rlmax))
        ts.append(max(0,dmin-rlmin))
if not nod and not nou:
        ts.append(max(0,(dmax-umax)/2))
        ts.append(max(0,(dmin-umin)/2))

ts = list(set(ts))
mn = BIG
for t in ts:
    mn = min(mn, foo(t))
print(mn)

Solution (Python):
from scipy.optimize import fmin
INF = 10**18
n = int(input())

xpoints = [[] for _ in range(3)]
ypoints = [[] for _ in range(3)]
for i in range(n):
    x, y, d = [item for item in input().split()]
    x = int(x); y = int(y)
    if d == "R":
        ypoints[0].append(y)
        xpoints[1].append(x)
    elif d == "L":
        ypoints[0].append(y)
        xpoints[2].append(x)
    elif d == "U":
        xpoints[0].append(x)
        ypoints[1].append(y)
    elif d == "D":
        xpoints[0].append(x)
        ypoints[2].append(y)
for i in range(3):
    xpoints[i].sort()
    ypoints[i].sort()

def f(t):
    if t < 0:
        return INF 
    max_x = max_y = -INF
    min_x = min_y = INF
    for i, a in enumerate([0, t, -t]):
        if not len(xpoints[i]) == 0:
            max_x = max(max_x, xpoints[i][-1] + a)
            min_x = min(min_x, xpoints[i][0] + a)
        if not len(ypoints[i]) == 0:
            max_y = max(max_y, ypoints[i][-1] + a)
            min_y = min(min_y, ypoints[i][0] + a)
    return (max_x - min_x) * (max_y - min_y)

ans = fmin(f, x0=10**8, ftol= 1e-9, disp=False)
print(f(ans[0]))

Solution (Python):
def men(t):
    xmin = min(st + i * t for i, st in enumerate(mg[0]))
    xmax = max(st + i * t for i, st in enumerate(mg[1]))
    ymin = min(st + i * t for i, st in enumerate(ue[0]))
    ymax = max(st + i * t for i, st in enumerate(ue[1]))
    return (xmax - xmin) * (ymax - ymin)

n = int(input())
inf = 10**9
mg = [[inf, inf, inf], [-inf, -inf, -inf]]
ue = [[inf, inf, inf], [-inf, -inf, -inf]]
mg0=mg[0]
mg1=mg[1]
ue0=ue[0]
ue1=ue[1]
for _ in range(n):
    x, y, d = input().split()
    x = int(x)
    y = int(y)
    if d == "U":
        mv = 1
        uv = 2
    elif d == "D":
        mv = 1
        uv = 0
    elif d == "R":
        mv = 2
        uv = 1
    else:
        mv = 0
        uv = 1
    if x < mg0[mv]: mg0[mv] = x
    if x > mg1[mv]: mg1[mv] = x
    if y < ue0[uv]: ue0[uv] = y
    if y > ue1[uv]: ue1[uv] = y
t=set([0])
for lst in [mg0,mg1,ue0,ue1]:
    v0,v1,v2=lst
    for tk in [v0-v1,v1-v2,(v0-v2)/2]:
        if tk>=0:
            t.add(tk)
print(min(men(tk) for tk in t))

Solution (Python):
N=int(input())
table=[]
for i in range(N):
    x,y,d=input().split()
    x,y=int(x),int(y)
    table.append((x,y,d))
anspos=[0]
inf=10**10
a=-inf
b=-inf
c=-inf
for i in range(N):
    x,y,d=table[i]
    if d=='L':
        a=max(x,a)
    elif d=='R':
        b = max(x, b)
    else:
        c = max(x, c)


anspos+=[abs(a-b)/2,abs(a-c),abs(b-c)]
a=inf
b=inf
c=inf
for i in range(N):
    x,y,d=table[i]
    if d=='L':
        a=min(x,a)
    elif d=='R':
        b = min(x, b)
    else:
        c = min(x, c)
anspos+=[abs(a-b)/2,abs(a-c),abs(b-c)]
a=-inf
b=-inf
c=-inf
for i in range(N):
    x,y,d=table[i]
    if d=='U':
        a=max(y,a)
    elif d=='D':
        b = max(y, b)
    else:
        c = max(y, c)
anspos+=[abs(a-b)/2,abs(a-c),abs(b-c)]
a=inf
b=inf
c=inf
for i in range(N):
    x,y,d=table[i]
    if d=='D':
        a=min(y,a)
    elif d=='U':
        b = min(y, b)
    else:
        c = min(y, c)
ans=10**30
anspos+=[abs(a-b)/2,abs(a-c),abs(b-c)]

for t in anspos:
    xmax=-inf
    xmin=inf
    ymax=-inf
    ymin=inf
    for i in range(N):
        x, y, d = table[i]
        if d=='U':
            y+=t
        elif d=='D':
            y-=t
        elif d=='L':
            x-=t
        elif d=='R':
            x+=t
        xmax=max(xmax,x)
        xmin = min(xmin, x)
        ymax = max(ymax, y)
        ymin = min(ymin, y)
    kai=(xmax-xmin)*(ymax-ymin)
    
    ans=min(ans,kai)
print(ans)