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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    aa = [LS() for _ in range(n)]
    xi = collections.defaultdict(lambda: inf)
    xa = collections.defaultdict(lambda: -inf)
    yi = collections.defaultdict(lambda: inf)
    ya = collections.defaultdict(lambda: -inf)
    km = 0
    for x,y,d in aa:
        x = int(x)
        y = int(y)
        if km < abs(x):
            km = abs(x)
        if km < abs(y):
            km = abs(y)
        if xi[d] > x:
            xi[d] = x
        if xa[d] < x:
            xa[d] = x
        if yi[d] > y:
            yi[d] = y
        if ya[d] < y:
            ya[d] = y

    ts = set([0])

    for d in [xi,xa,yi,ya]:
        ks = list(d.keys())
        for k in ks:
            for e in ks:
                ts.add(abs(d[k] - d[e]))
                ts.add(abs(d[k] - d[e]) / 2)

    def f(i):
        xxi = inf
        xxa = -inf
        yyi = inf
        yya = -inf
        for d,x in xi.items():
            if d == 'L':
                x -= i
            elif d == 'R':
                x += i
            if xxi > x:
                xxi = x
        for d,x in xa.items():
            if d == 'L':
                x -= i
            elif d == 'R':
                x += i
            if xxa < x:
                xxa = x
        for d,y in yi.items():
            if d == 'D':
                y -= i
            elif d == 'U':
                y += i
            if yyi > y:
                yyi = y
        for d,y in ya.items():
            if d == 'D':
                y -= i
            elif d == 'U':
                y += i
            if yya < y:
                yya = y

        return (xxa-xxi) * (yya-yyi)

    r = f(0)
    for i in ts:
        t = f(i)
        if r > t:
            r = t

    return '{:0.3f}'.format(r)


print(main())

Solution (Python):

from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import random
import collections
import math
import itertools
import bisect

def real_main():
    n = read_int()
    x, y, d = [], [], []
    for _ in range(n):
        s = read_array()
        x.append(int(s[0]))
        y.append(int(s[1]))
        d.append(s[2])
        
        
        
        
        
        
        
        
        
        
        
        

    print(solve(x, y, d))

def solve(x, y, d):
    
    y_max = [float('-inf')]*3
    x_max = [float('-inf')]*3
    x_min = [float('inf')]*3
    y_min = [float('inf')]*3
    for x, y, d in zip(x, y, d):
        if d == 'R' or d == 'L':
            y_max[2] = max(y_max[2], y)
            y_min[2] = min(y_min[2], y)
        if d == 'U' or d == 'D':
            x_max[2] = max(x_max[2], x)
            x_min[2] = min(x_min[2], x)

        if d == 'U':
            y_max[0] = max(y_max[0], y)
            y_min[1] = min(y_min[1], y)
        elif d == 'D':
            y_min[0] = min(y_min[0], y)
            y_max[1] = max(y_max[1], y)
        elif d == 'R':
            x_max[0] = max(x_max[0], x)
            x_min[1] = min(x_min[1], x)
        else:
            x_min[0] = min(x_min[0], x)
            x_max[1] = max(x_max[1], x)

    def score_at(t):
        ymax = max(y_max[0] + t, y_max[1] - t, y_max[2])
        xmax = max(x_max[0] + t, x_max[1] - t, x_max[2])

        ymin = min(y_min[0] - t, y_min[1] + t, y_min[2])
        xmin = min(x_min[0] - t, x_min[1] + t, x_min[2])

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

    lo, hi = 0, 10**8
    while hi - lo > 0.000001:
        mid_left = lo * 2 / 3 + hi / 3
        mid_right = lo / 3 + hi * 2 / 3
        if score_at(mid_left) >= score_at(mid_right):
            lo = mid_left
        else:
            hi = mid_right

    return score_at(round(hi, 3))



def main():
    if False and 'PYCHARM_HOSTED' in os.environ:
        main_pycharm()
    else:
        real_main()


from copy import deepcopy
def main_pycharm():
    solution = solve

    test_inputs = None
    test_outputs = None
    judge = None
    slow_solution = None
    if solution is not None:
        if test_outputs is not None:
            test_with_answers(solution, test_inputs, test_outputs)
        if judge is not None:
            test_with_judge(solution, test_inputs, judge)
        if slow_solution is not None:
            test_with_slow_solution(solution, test_inputs, slow_solution)


def test_with_answers(solution, inputs_answers):
    total, wrong = 0, 0
    for args, test_ans in inputs_answers:
        ans = solution(*args.copy())
        if ans != test_ans:
            print('WRONG! ans=%s, test_ans=%s, args=%s' % (ans, test_ans, args))
            wrong += 1
        else:
            print('GOOD')
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_judge(solution, inputs_gen, judge):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        if not judge(deepcopy(ans), *deepcopy(args)):
            print('WRONG! ans=%s, args=%s' % (ans, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_slow_solution(solution, inputs_gen, solution_slow):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        slow = solution_slow(*deepcopy(args))
        if ans != slow:
            print('WRONG! ans=%s, slow=%s, args=%s' % (ans, slow, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

def read():
    return input()

def read_int():
    return int(input())

def read_array(sep=None, maxsplit=-1):
    return input().split(sep, maxsplit)

def read_int_array():
    return [int(a) for a in read_array()]



if __name__ == "__main__":
    main()

Solution (Python):
import sys
from scipy.optimize import fmin

input = sys.stdin.readline

n = int(input())

XR = []
XL = []
XS = []
YU = []
YD = []
YS = []

for _ in range(n):
    x, y, d = input().split()
    x = int(x)
    y = int(y)
    if d == "D":
        XS.append(x)
        YD.append(y)
    elif d == "U":
        XS.append(x)
        YU.append(y)
    elif d == "R":
        XR.append(x)
        YS.append(y)
    elif d == "L":
        XL.append(x)
        YS.append(y)

max_YD = max(YD + [float("-inf")])
max_YS = max(YS + [float("-inf")])
max_YU = max(YU + [float("-inf")])
min_YD = min(YD + [float("inf")])
min_YS = min(YS + [float("inf")])
min_YU = min(YU + [float("inf")])

max_XR = max(XR + [float("-inf")])
max_XL = max(XL + [float("-inf")])
max_XS = max(XS + [float("-inf")])
min_XR = min(XR + [float("inf")])
min_XL = min(XL + [float("inf")])
min_XS = min(XS + [float("inf")])


def diff_xy(t):
    if t < 0:
        return float("inf")
    diff_y = max(max_YD - t, max_YU + t, max_YS) - min(min_YD - t, min_YU + t, min_YS)
    diff_x = max(max_XL - t, max_XR + t, max_XS) - min(min_XL - t, min_XR + t, min_XS)
    return diff_x * diff_y


def binary_search(min_t, max_t):
    mid_t = (min_t + max_t) / 2
    if max_t - min_t < 10 ** (-10):
        return diff_xy(mid_t)

    if diff_xy(min_t) < diff_xy(mid_t):
        return binary_search(min_t, mid_t)
    elif diff_xy(max_t) < diff_xy(mid_t):
        return binary_search(mid_t, max_t)
    else:
        return opt(min_t, mid_t, max_t)


def opt(a, b, c):
    optimal_a = fmin(diff_xy, a, full_output=False, disp=False, xtol=10 ** (-10))
    optimal_b = fmin(diff_xy, b, full_output=False, disp=False, xtol=10 ** (-10))
    optimal_c = fmin(diff_xy, c, full_output=False, disp=False, xtol=10 ** (-10))
    ans = min(diff_xy(optimal_a[0]), diff_xy(optimal_b[0]), diff_xy(optimal_c[0]))
    return (ans)


print(binary_search(0, 2 * 10 ** 8))

Solution (Python):

from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import random
import collections
import math
import itertools
import bisect

def real_main():
    n = read_int()
    x, y, d = [], [], []
    for _ in range(n):
        s = read_array()
        x.append(int(s[0]))
        y.append(int(s[1]))
        d.append(s[2])
        
        
        
        
        
        
        
        
        
        
        
        

    print(solve(x, y, d))

def solve(x, y, d):
    
    y_max = [float('-inf')]*3
    x_max = [float('-inf')]*3
    x_min = [float('inf')]*3
    y_min = [float('inf')]*3
    for x, y, d in zip(x, y, d):
        if d == 'R' or d == 'L':
            y_max[2] = max(y_max[2], y)
            y_min[2] = min(y_min[2], y)
        if d == 'U' or d == 'D':
            x_max[2] = max(x_max[2], x)
            x_min[2] = min(x_min[2], x)

        if d == 'U':
            y_max[0] = max(y_max[0], y)
            y_min[1] = min(y_min[1], y)
        elif d == 'D':
            y_min[0] = min(y_min[0], y)
            y_max[1] = max(y_max[1], y)
        elif d == 'R':
            x_max[0] = max(x_max[0], x)
            x_min[1] = min(x_min[1], x)
        else:
            x_min[0] = min(x_min[0], x)
            x_max[1] = max(x_max[1], x)

    def score_at(t):
        ymax = max(y_max[0] + t, y_max[1] - t, y_max[2])
        xmax = max(x_max[0] + t, x_max[1] - t, x_max[2])

        ymin = min(y_min[0] - t, y_min[1] + t, y_min[2])
        xmin = min(x_min[0] - t, x_min[1] + t, x_min[2])

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

    lo, hi = 0, 10**8
    while hi - lo > 0.000001:
        mid_left = lo * 2 / 3 + hi / 3
        mid_right = lo / 3 + hi * 2 / 3
        if score_at(mid_left) >= score_at(mid_right):
            lo = mid_left
        else:
            hi = mid_right

    return score_at(round(hi, 3))



def main():
    if False and 'PYCHARM_HOSTED' in os.environ:
        main_pycharm()
    else:
        real_main()


from copy import deepcopy
def main_pycharm():
    solution = solve

    test_inputs = None
    test_outputs = None
    judge = None
    slow_solution = None
    if solution is not None:
        if test_outputs is not None:
            test_with_answers(solution, test_inputs, test_outputs)
        if judge is not None:
            test_with_judge(solution, test_inputs, judge)
        if slow_solution is not None:
            test_with_slow_solution(solution, test_inputs, slow_solution)


def test_with_answers(solution, inputs_answers):
    total, wrong = 0, 0
    for args, test_ans in inputs_answers:
        ans = solution(*args.copy())
        if ans != test_ans:
            print('WRONG! ans=%s, test_ans=%s, args=%s' % (ans, test_ans, args))
            wrong += 1
        else:
            print('GOOD')
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_judge(solution, inputs_gen, judge):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        if not judge(deepcopy(ans), *deepcopy(args)):
            print('WRONG! ans=%s, args=%s' % (ans, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_slow_solution(solution, inputs_gen, solution_slow):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        slow = solution_slow(*deepcopy(args))
        if ans != slow:
            print('WRONG! ans=%s, slow=%s, args=%s' % (ans, slow, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

def read():
    return input()

def read_int():
    return int(input())

def read_array(sep=None, maxsplit=-1):
    return input().split(sep, maxsplit)

def read_int_array():
    return [int(a) for a in read_array()]



if __name__ == "__main__":
    main()

Solution (Python):



import sys
n = int(input())

inf = float("inf")
u=d=l=r=0
umin = inf
umax = -inf
dmin = inf
dmax = -inf
lmin = inf
lmax = -inf
rmin = inf
rmax = -inf
xmin = inf
xmax = -inf
ymin = inf
ymax = -inf
xx=yy=0

for j in range(n):
    x,y,D = [i for i in input().split()]
    x=int(x); y=int(y)
    if D == "U":
        umin = min(umin,y)
        umax = max(umax,y)
        u=1
        xmin = min(xmin,x)
        xmax = max(xmax,x)
        xx=1
    if D == "D":
        dmin = min(dmin,y)
        dmax = max(dmax,y)
        d=1
        xmin = min(xmin,x)
        xmax = max(xmax,x)
        xx=1
    if D == "L":
        lmin = min(lmin,x)
        lmax = max(lmax,x)
        l=1
        ymin = min(ymin,y)
        ymax = max(ymax,y)
        yy=1
    if D == "R":
        rmin = min(rmin,x)
        rmax = max(rmax,x)
        r=1
        ymin = min(ymin,y)
        ymax = max(ymax,y)
        yy=1

def lpos(t):
    ans = inf
    if xx: ans = min(ans,xmin)
    if l: ans = min(ans,lmin-t)
    if r: ans = min(ans,rmin+t)
    return ans
def rpos(t):
    ans = -inf
    if xx: ans = max(ans,xmax)
    if l: ans = max(ans,lmax-t)
    if r: ans = max(ans,rmax+t)
    return ans

def dpos(t):
    ans = inf
    if yy: ans = min(ans,ymin)
    if u: ans = min(ans,umin+t)
    if d: ans = min(ans,dmin-t)
    return ans
def upos(t):
    ans = -inf
    if yy: ans = max(ans,ymax)
    if u: ans = max(ans,umax+t)
    if d: ans = max(ans,dmax-t)
    return ans

s = {0}
if xx and l:
    if lmin - xmin > 0: s.add(lmin - xmin)
    if lmax - xmax > 0: s.add(lmax - xmax)
if xx and r:
    if xmin - rmin > 0: s.add(xmin - rmin)
    if xmax - rmax > 0: s.add(xmax - rmax)
if l and r:
    if lmin-rmin > 0: s.add((lmin-rmin)/2)
    if lmax-rmax > 0: s.add((lmax-rmax)/2)

if yy and d:
    if dmin - ymin > 0: s.add(dmin - ymin)
    if dmax - ymax > 0: s.add(dmax - ymax)
if yy and u:
    if ymin - umin > 0: s.add(ymin - umin)
    if ymax - umax > 0: s.add(ymax - umax)
if d and u:
    if dmin-umin > 0: s.add((dmin-umin)/2)
    if dmax-umax > 0: s.add((dmax-umax)/2)
    


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 sys
from scipy.optimize import fmin

input = sys.stdin.readline

n = int(input())

XR = []
XL = []
XS = []
YU = []
YD = []
YS = []

for _ in range(n):
    x, y, d = input().split()
    x = int(x)
    y = int(y)
    if d == "D":
        XS.append(x)
        YD.append(y)
    elif d == "U":
        XS.append(x)
        YU.append(y)
    elif d == "R":
        XR.append(x)
        YS.append(y)
    elif d == "L":
        XL.append(x)
        YS.append(y)


max_YD = max(YD + [float("-inf")])
max_YS = max(YS + [float("-inf")])
max_YU = max(YU + [float("-inf")])
min_YD = min(YD + [float("inf")])
min_YS = min(YS + [float("inf")])
min_YU = min(YU + [float("inf")])

max_XR = max(XR + [float("-inf")])
max_XL = max(XL + [float("-inf")])
max_XS = max(XS + [float("-inf")])
min_XR = min(XR + [float("inf")])
min_XL = min(XL + [float("inf")])
min_XS = min(XS + [float("inf")])


def diff_xy(t):
    diff_y = max(max_YD - t, max_YU + t, max_YS) - min(min_YD - t, min_YU + t, min_YS)
    diff_x = max(max_XL - t, max_XR + t, max_XS) - min(min_XL - t, min_XR + t, min_XS)
    return diff_x * diff_y


options = [
    max_YD - max_YS,
    max_YS - max_YU,
    (max_YD - max_YU) / 2,
    min_YD - min_YS,
    (min_YD - min_YU) / 2,
    min_YS - min_YU,
    max_XL - max_XS,
    max_XS - max_XR,
    (max_XL - max_XR) / 2,
    min_XL - min_XS,
    (min_XL - min_XR) / 2,
    min_XS - min_XR]

ans = diff_xy(0)

for option in options:
    if option >= 0:
        ans = min(ans, diff_xy(option))

print(ans)

Solution (Python):
def analyze(points, left_static, right_static):
    """
    (x0, +1 or -1) in points
    """

    rightest_neg = -10**9
    leftest_neg = 10**9
    rightest_pos = -10**9
    leftest_pos = 10**9
    for x, d in points:
        if d == 1:
            rightest_pos = max(rightest_pos, x)
            leftest_pos = min(leftest_pos, x)
        else:
            rightest_neg = max(rightest_neg, x)
            leftest_neg = min(leftest_neg, x)


    max_t1 = rightest_neg - right_static
    max_t2 = right_static - rightest_pos
    if max_t1 > max_t2:
        max_t1 = max_t2 = (rightest_neg-rightest_pos)/2
    max_t1 = max(0, max_t1)
    max_t2 = max(0, max_t2)
    max_x0 = max(rightest_pos, rightest_neg, right_static)
    max_x1 = max(rightest_pos + max_t1, rightest_neg - max_t1, right_static)
    def get_xmax(t):
        if t > max_t2:
            return max_x1 + t-max_t2
        elif t > max_t1:
            return max_x1
        else:
            return max_x0 - t

    min_t1 = left_static - leftest_pos
    min_t2 = leftest_neg - left_static
    if min_t1 > min_t2:
        min_t1 = min_t2 = (leftest_neg - leftest_pos)/2
    min_t1 = max(0, min_t1)
    min_t2 = max(0, min_t2)
    min_x0 = min(leftest_pos, leftest_neg, left_static)
    min_x1 = min(leftest_pos + min_t1, leftest_neg - min_t1, left_static)

    def get_xmin(t):
        if t > min_t2:
            return min_x1 - t + min_t2
        elif t > min_t1:
            return min_x1
        else:
            return min_x0 + t

    T = sorted((max_t1, max_t2, min_t1, min_t2))
    D = [get_xmax(t)-get_xmin(t) for t in T]
    return T,D



N = int(input())

conv = {'R':0,'U':1,'L':2,'D':3}
points = [(lambda i: (int(i[0]), int(i[1]), conv[i[2]]))(input().split()) for _ in range(N)]


xt, xd = analyze([(x, 1 if d == 0 else -1) for x,y,d in points if d%2==0],
                    min((x for x,y,d in points if d%2==1), default=10**9),
                    max((x for x,y,d in points if d%2==1), default=-10**9))

yt, yd = analyze([(y, 1 if d == 1 else -1) for x,y,d in points if d%2==1],
                    min((y for x,y,d in points if d%2==0), default=10**9),
                    max((y for x,y,d in points if d%2==0), default=-10**9))

def get_w(t):
    a,b,c,d = xt

    if t < a:
        return -2, xd[0] + 2*a
    elif t < b:
        return -1, xd[0] + a
    elif t < c:
        return 0, xd[1]
    elif t < d:
        return 1, xd[2] - c
    else:
        return 2, xd[3] - 2*d

def get_h(t):
    a,b,c,d = yt

    if t < a:
        return -2, yd[0] + 2*a
    elif t < b:
        return -1, yd[0] + a
    elif t < c:
        return 0, yd[1]
    elif t < d:
        return 1, yd[2] - c
    else:
        return 2, yd[3] - 2*d

T = sorted(xt+yt)

def it():
    ne = iter(T)
    next(ne)
    for a,b in zip(T,ne):
        t = (a+b)/2

        wa, wb = get_w(t)
        ha, hb = get_h(t)
        if wa*ha > 0 and a < -(wb*ha+wa*hb)/(2*wa*ha) < b:
            t = -(wb*ha+wa*hb)/(2*wa*ha)
            yield ((wa*t+wb)*(ha*t+hb), t)
        else:
            yield ((wa*a+wb)*(ha*a+hb), a)
            yield ((wa*b+wb)*(ha*b+hb), b)

print(min(it())[0])

Solution (Python):
INF = float('inf')

N = int(input())

xConstMin, xConstMax = INF, -INF
xAscMin, xAscMax = INF, -INF
xDescMin, xDescMax = INF, -INF
yConstMin, yConstMax = INF, -INF
yAscMin, yAscMax = INF, -INF
yDescMin, yDescMax = INF, -INF
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    if d == 'R':
        xAscMax = max(xAscMax, x)
        xAscMin = min(xAscMin, x)
        yConstMax = max(yConstMax, y)
        yConstMin = min(yConstMin, y)
    elif d == 'L':
        xDescMax = max(xDescMax, x)
        xDescMin = min(xDescMin, x)
        yConstMax = max(yConstMax, y)
        yConstMin = min(yConstMin, y)
    elif d == 'U':
        xConstMax = max(xConstMax, x)
        xConstMin = min(xConstMin, x)
        yAscMax = max(yAscMax, y)
        yAscMin = min(yAscMin, y)
    elif d == 'D':
        xConstMax = max(xConstMax, x)
        xConstMin = min(xConstMin, x)
        yDescMax = max(yDescMax, y)
        yDescMin = min(yDescMin, y)

tms = []

t1 = max(0, xDescMax - xConstMax)
t2 = max(0, xConstMax - xAscMax)
if t1 >= t2:
    t = max(0, (xDescMax-xAscMax)/2)
    tms.append(t)
else:
    tms.append(t1)
    tms.append(t2)

t1 = max(0, xConstMin - xAscMin)
t2 = max(0, xDescMin - xConstMin)
if t1 >= t2:
    t = max(0, (xDescMin-xAscMin)/2)
    tms.append(t)
else:
    tms.append(t1)
    tms.append(t2)

t1 = max(0, yDescMax - yConstMax)
t2 = max(0, yConstMax - yAscMax)
if t1 >= t2:
    t = max(0, (yDescMax-yAscMax)/2)
    tms.append(t)
else:
    tms.append(t1)
    tms.append(t2)

t1 = max(0, yConstMin - yAscMin)
t2 = max(0, yDescMin - yConstMin)
if t1 >= t2:
    t = max(0, (yDescMin-yAscMin)/2)
    tms.append(t)
else:
    tms.append(t1)
    tms.append(t2)

ans = INF
for tm in tms:
    if tm == INF: continue

    xs = [xConstMin, xConstMax, xAscMin+tm, xAscMax+tm, xDescMin-tm, xDescMax-tm]
    ys = [yConstMin, yConstMax, yAscMin+tm, yAscMax+tm, yDescMin-tm, yDescMax-tm]

    xMin, xMax = INF, -INF
    for x in xs:
        if x == INF or x == -INF: continue
        xMin = min(xMin, x)
        xMax = max(xMax, x)

    yMin, yMax = INF, -INF
    for y in ys:
        if y == INF or y == -INF: continue
        yMin = min(yMin, y)
        yMax = max(yMax, y)

    ans = min(ans, (xMax-xMin)*(yMax-yMin))

print(ans)

Solution (Python):
inf = float("inf")
N = int(input())
if N==1:
    print(0)
    exit()
lr = inf
ll = inf
rr = -inf
rl = -inf
ud = -inf
uu = -inf
dd = inf
du = inf
l_stop = inf
r_stop = -inf
u_stop = -inf
d_stop = inf
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    if d=="R":
        lr = min(lr, x)
        rr = max(rr, x)
    elif d=="L":
        rl = max(rl, x)
        ll = min(ll, x)
    elif d=="U":
        du = min(du, y)
        uu = max(uu, y)
    else:
        ud = max(ud, y)
        dd = min(dd, y)
    if d=="R" or d=="L":
        u_stop = max(u_stop, y)
        d_stop = min(d_stop, y)
    else:
        l_stop = min(l_stop, x)
        r_stop = max(r_stop, x)


def f(t):
    r = max(r_stop, rr+t, rl-t)
    l = min(l_stop, ll-t, lr+t)
    u = max(u_stop, uu+t, ud-t)
    d = min(d_stop, dd-t, du+t)
    return (r-l) * (u-d)


high = 10**8
high = float(high)
low = 0.0
while high - low > 0.000001:
    
    mid_left = high/3+low*2/3
    mid_right = high*2/3+low/3
    if f(mid_left) >= f(mid_right):
        low = mid_left
    else:
        high = mid_right
print(f(round(high, 3)))

Solution (Python):
import sys
input = sys.stdin.readline

N=int(input())
P=[input().split() for i in range(N)]

for i in range(N):
    P[i][0]=int(P[i][0])
    P[i][1]=int(P[i][1])

def ans(Q):
    MINX=10**15
    MAXX=-10**15
    MINY=10**15
    MAXY=-10**15

    for x,y in Q:
        MINX=min(MINX,x)
        MINY=min(MINY,y)
        MAXX=max(MAXX,x)
        MAXY=max(MAXY,y)

    return (MAXX-MINX)*(MAXY-MINY)
    
def time(t):
    Q=[]
    for x,y,s in P:
        if s=="R":
            x+=t
        elif s=="L":
            x-=t
        elif s=="U":
            y+=t
        else:
            y-=t
        Q.append([x,y])

    return Q

MIN=0
MAX=10**10

while MAX-MIN>=1:
    
    x=(MIN+MAX)//2

    if ans(time(x))>ans(time(x+1/2)):
        MIN=x+1/2
    else:
        MAX=x

        
print(min(ans(time(MAX)),ans(time(MIN))))