Problem: 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.

Submission attempts (in order):
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**9, ftol = 10**-10, disp = False)
print(f(xopt[0]))

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):
    return dx(t)*dy(t)
xopt = fmin(f, x0 = 10**8, ftol = 10**-9, disp = False)
print(f(xopt[0]))













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**9, ftol = 10**-10, disp = False)
print(f(xopt[0]))

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)















Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted