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):
import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    inf = 10**8 + 1
    err = 10**(-9)
    N = int(input())
    x_max = [-inf, -inf, -inf]  
    x_min = [inf, inf, inf]     
    y_max = [-inf, -inf, -inf]  
    y_min = [inf, inf, inf]     
    for _ in range(N):
        x, y, d = map(str, input().strip().split())
        x, y = int(x), int(y)

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

    def get_val(t):
        x0 = max(x_max[0], x_max[1]+t, x_max[2]-t)
        x1 = min(x_min[0], x_min[1]+t, x_min[2]-t)
        y0 = max(y_max[0], y_max[1]+t, y_max[2]-t)
        y1 = min(y_min[0], y_min[1]+t, y_min[2]-t)

        return (x0 - x1) * (y0 - y1)

    left, right = 0, 5*inf + 1
    mid = (left + right) / 2
    while True:
        lv = get_val(left)
        rv = get_val(right)
        mv = get_val(mid)

        max_val = max(lv, rv, mv)
        min_val = min(lv, rv, mv)
        if max_val - min_val < err:
            return get_val(mid)

        if mv == min_val:
            left_ = (left + mid) / 2
            right_ = (right + mid) / 2
            if mv <= get_val(left_):
                left = left_
            if mv <= get_val(right):
                right = right_
            mid = (left + right) / 2
        elif lv == min_val:
            right = mid
            mid = (left + right) / 2
        else:
            left = mid
            mid = (left + right) / 2

    return get_val(mid)


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


import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    inf = 2 * 10**8
    err = 10**(-9)
    N = int(input())
    x_max = [-inf, -inf, -inf]  
    x_min = [inf, inf, inf]     
    y_max = [-inf, -inf, -inf]  
    y_min = [inf, inf, inf]     
    for _ in range(N):
        x, y, d = map(str, input().strip().split())
        x, y = int(x), int(y)

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

    def f(t):
        x0 = max(x_max[0], x_max[1]+t, x_max[2]-t)
        x1 = min(x_min[0], x_min[1]+t, x_min[2]-t)
        y0 = max(y_max[0], y_max[1]+t, y_max[2]-t)
        y1 = min(y_min[0], y_min[1]+t, y_min[2]-t)
        
        return (x0 - x1) * (y0 - y1)

    left, right = 0, inf
    mid = (left + right) / 2
    while max(f(left), f(right), f(mid)) - min(f(left), f(right), f(mid)) > err:
        lv = f(left)
        rv = f(right)
        mv = f(mid)

        min_val = min(lv, rv, mv)
        if mv == min_val:
            left = (left + mid) / 2
            right = (right + mid) / 2
            mid = (left + right) / 2
        elif lv == min_val:
            right = mid
            mid = (left + right) / 2
        else:
            left = mid
            mid = (left + right) / 2

    return f(mid)


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


import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    inf = 2 * 10**8
    err = 10**(-9)
    N = int(input())
    x_max = [-inf, -inf, -inf]  
    x_min = [inf, inf, inf]     
    y_max = [-inf, -inf, -inf]  
    y_min = [inf, inf, inf]     
    for _ in range(N):
        x, y, d = map(str, input().strip().split())
        x, y = int(x), int(y)

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

    def get_val(t):
        x0 = max(x_max[0], x_max[1]+t, x_max[2]-t)
        x1 = min(x_min[0], x_min[1]+t, x_min[2]-t)
        y0 = max(y_max[0], y_max[1]+t, y_max[2]-t)
        y1 = min(y_min[0], y_min[1]+t, y_min[2]-t)

        return (x0 - x1) * (y0 - y1)

    left, right = 0, inf
    mid = (left + right) / 2
    while True:
        lv = get_val(left)
        rv = get_val(right)
        mv = get_val(mid)

        max_val = max(lv, rv, mv)
        min_val = min(lv, rv, mv)
        if max_val - min_val < err:
            return get_val(mid)

        if mv == min_val:
            left_ = (left + mid) / 2
            right_ = (right + mid) / 2
            if mv < get_val(left_):
                left = left_
            if mv < get_val(right):
                right = right_
            mid = (left + right) / 2
        elif lv == min_val:
            right = mid
            mid = (left + right) / 2
        else:
            left = mid
            mid = (left + right) / 2

    return get_val(mid)


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


import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    inf = 10**8 + 1
    err = 10**(-9)
    N = int(input())
    x_max = [-inf, -inf, -inf]  
    x_min = [inf, inf, inf]     
    y_max = [-inf, -inf, -inf]  
    y_min = [inf, inf, inf]     
    for _ in range(N):
        x, y, d = map(str, input().strip().split())
        x, y = int(x), int(y)

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

    def get_val(t):
        x0 = max(x_max[0], x_max[1]+t, x_max[2]-t)
        x1 = min(x_min[0], x_min[1]+t, x_min[2]-t)
        y0 = max(y_max[0], y_max[1]+t, y_max[2]-t)
        y1 = min(y_min[0], y_min[1]+t, y_min[2]-t)

        return (x0 - x1) * (y0 - y1)

    left, right = 0, 2*inf + 1
    mid = (left + right) / 2
    while True:
        lv = get_val(left)
        rv = get_val(right)
        mv = get_val(mid)

        max_val = max(lv, rv, mv)
        min_val = min(lv, rv, mv)
        if max_val - min_val < err:
            return get_val(mid)

        if mv == min_val:
            left_ = (left + mid) / 2
            right_ = (right + mid) / 2
            if mv <= get_val(left_):
                left = left_
            if mv <= get_val(right):
                right = right_
            mid = (left + right) / 2
        elif lv == min_val:
            right = mid
            mid = (left + right) / 2
        else:
            left = mid
            mid = (left + right) / 2

    return get_val(mid)


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


import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    inf = 10**8 + 1
    err = 10**(-9)
    N = int(input())
    x_max = [-inf, -inf, -inf]  
    x_min = [inf, inf, inf]     
    y_max = [-inf, -inf, -inf]  
    y_min = [inf, inf, inf]     
    for _ in range(N):
        x, y, d = map(str, input().strip().split())
        x, y = int(x), int(y)

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

    def get_val(t):
        x0 = max(x_max[0], x_max[1]+t, x_max[2]-t)
        x1 = min(x_min[0], x_min[1]+t, x_min[2]-t)
        y0 = max(y_max[0], y_max[1]+t, y_max[2]-t)
        y1 = min(y_min[0], y_min[1]+t, y_min[2]-t)

        return (x0 - x1) * (y0 - y1)

    left, right = 0, 2*inf
    mid = (left + right) / 2
    while True:
        lv = get_val(left)
        rv = get_val(right)
        mv = get_val(mid)

        max_val = max(lv, rv, mv)
        min_val = min(lv, rv, mv)
        if max_val - min_val < err:
            return get_val(mid)

        if mv == min_val:
            left_ = (left + mid) / 2
            right_ = (right + mid) / 2
            if mv <= get_val(left_):
                left = left_
            if mv <= get_val(right):
                right = right_
            mid = (left + right) / 2
        elif lv == min_val:
            right = mid
            mid = (left + right) / 2
        else:
            left = mid
            mid = (left + right) / 2

    return get_val(mid)


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


import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    inf = 10**8 + 1
    err = 10**(-9)
    N = int(input())
    x_max = [-inf, -inf, -inf]  
    x_min = [inf, inf, inf]     
    y_max = [-inf, -inf, -inf]  
    y_min = [inf, inf, inf]     
    for _ in range(N):
        x, y, d = map(str, input().strip().split())
        x, y = int(x), int(y)

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

    def get_val(t):
        x0 = max(x_max[0], x_max[1]+t, x_max[2]-t)
        x1 = min(x_min[0], x_min[1]+t, x_min[2]-t)
        y0 = max(y_max[0], y_max[1]+t, y_max[2]-t)
        y1 = min(y_min[0], y_min[1]+t, y_min[2]-t)

        return (x0 - x1) * (y0 - y1)

    left, right = 0, 2*inf + 1
    mid = (left + right) / 2
    while True:
        lv = get_val(left)
        rv = get_val(right)
        mv = get_val(mid)

        max_val = max(lv, rv, mv)
        min_val = min(lv, rv, mv)
        if max_val - min_val < err:
            return get_val(mid)

        if mv == min_val:
            left_ = (left + mid) / 2
            right_ = (right + mid) / 2
            if mv <= get_val(left_):
                left = left_
            if mv <= get_val(right):
                right = right_
            mid = (left + right) / 2
        elif lv == min_val:
            right = mid
            mid = (left + right) / 2
        else:
            left = mid
            mid = (left + right) / 2

    return get_val(mid)


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


import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    inf = 2 * 10**8
    err = 10**(-9)
    N = int(input())
    x_max = [-inf, -inf, -inf]  
    x_min = [inf, inf, inf]     
    y_max = [-inf, -inf, -inf]  
    y_min = [inf, inf, inf]     
    for _ in range(N):
        x, y, d = map(str, input().strip().split())
        x, y = int(x), int(y)

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

    def get_val(t):
        x0 = max(x_max[0], x_max[1]+t, x_max[2]-t)
        x1 = min(x_min[0], x_min[1]+t, x_min[2]-t)
        y0 = max(y_max[0], y_max[1]+t, y_max[2]-t)
        y1 = min(y_min[0], y_min[1]+t, y_min[2]-t)

        return (x0 - x1) * (y0 - y1)

    left, right = 0, inf
    mid = (left + right) / 2
    while True:
        lv = get_val(left)
        rv = get_val(right)
        mv = get_val(mid)

        max_val = max(lv, rv, mv)
        min_val = min(lv, rv, mv)
        if max_val - min_val < err:
            return get_val(mid)

        if mv == min_val:
            left_ = (left + mid) / 2
            right_ = (right + mid) / 2
            if mv <= get_val(left_):
                left = left_
            if mv <= get_val(right):
                right = right_
            mid = (left + right) / 2
        elif lv == min_val:
            right = mid
            mid = (left + right) / 2
        else:
            left = mid
            mid = (left + right) / 2

    return get_val(mid)


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


import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    inf = 10**8 + 1
    err = 10**(-10)
    N = int(input())
    x_max = [-inf, -inf, -inf]  
    x_min = [inf, inf, inf]     
    y_max = [-inf, -inf, -inf]  
    y_min = [inf, inf, inf]     
    for _ in range(N):
        x, y, d = map(str, input().strip().split())
        x, y = int(x), int(y)

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

    def get_val(t):
        x0 = max(x_max[0], x_max[1]+t, x_max[2]-t)
        x1 = min(x_min[0], x_min[1]+t, x_min[2]-t)
        y0 = max(y_max[0], y_max[1]+t, y_max[2]-t)
        y1 = min(y_min[0], y_min[1]+t, y_min[2]-t)

        return (x0 - x1) * (y0 - y1)

    left, right = 0, 2*inf + 1
    mid = (left + right) / 2
    while True:
        lv = get_val(left)
        rv = get_val(right)
        mv = get_val(mid)

        max_val = max(lv, rv, mv)
        min_val = min(lv, rv, mv)
        if max_val - min_val < err:
            return get_val(mid)

        if mv == min_val:
            left_ = (left + mid) / 2
            right_ = (right + mid) / 2
            if mv <= get_val(left_):
                left = left_
            if mv <= get_val(right):
                right = right_
            mid = (left + right) / 2
        elif lv == min_val:
            right = mid
            mid = (left + right) / 2
        else:
            left = mid
            mid = (left + right) / 2

    return get_val(mid)


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


import sys

def main():
    input = sys.stdin.readline
    inf = 10**8 + 1
    N = int(input())
    const_x_max, right_max, left_max = -inf, -inf, -inf
    const_x_min, right_min, left_min = inf, inf, inf
    const_y_max, up_max, down_max = -inf, -inf, -inf
    const_y_min, up_min, down_min = inf, inf, inf
    for _ in range(N):
        x, y, d = map(str, input().strip().split())
        x, y = int(x), int(y)

        if d == 'R':
            right_max = max(right_max, x)
            right_min = min(right_min, x)
            const_y_max = max(const_y_max, y)
            const_y_min = min(const_y_min, y)
        elif d == 'L':
            left_max = max(left_max, x)
            left_min = min(left_min, x)
            const_y_max = max(const_y_max, y)
            const_y_min = min(const_y_min, y)
        elif d == 'U':
            const_x_max = max(const_x_max, x)
            const_x_min = min(const_x_min, x)
            up_max = max(up_max, y)
            up_min = min(up_min, y)
        else:
            const_x_max = max(const_x_max, x)
            const_x_min = min(const_x_min, x)
            down_max = max(down_max, y)
            down_min = min(down_min, y)

    inflections = set([0])
    # The time when the slope of max_x changes.
    # 1. from decrease to constant.
    inflections.add(max(0, left_max - const_x_max))
    # 2. from decrease to increase.
    inflections.add(max(0, (left_max - right_max)/2))
    # 3. from constant to increase.
    inflections.add(max(0, const_x_max - right_max))

    # The time when the slope of min_x changes.
    # 4. from increase to constatnt.
    inflections.add(max(0, const_x_min - right_min))
    # 5. from increase to decrease.
    inflections.add(max(0, (left_min - right_min)/2))
    # 6. from constant to decrease.
    inflections.add(max(0, left_min - const_x_min))

    # The time when the slope of max_y changes.
    # 7. from decrease to constant.
    inflections.add(max(0, down_max - const_y_max))
    # 8. from decrease to increase.
    inflections.add(max(0, (down_max - up_max)/2))
    # 9. from constant to increase.
    inflections.add(max(0, const_y_max - up_max))

    # The time when the slope of min_y changes.
    # 10. from increase to constatnt.
    inflections.add(max(0, const_y_min - up_min))
    # 11. from increase to decrease.
    inflections.add(max(0, (down_min - up_min)/2))
    # 12. from constant to decrease.
    inflections.add(max(0, down_min - const_y_min))


    def get_val(t):
        x0 = max(const_x_max, right_max + t, left_max - t)
        x1 = min(const_x_min, right_min + t, left_min - t)
        y0 = max(const_y_max, up_max + t, down_max - t)
        y1 = min(const_y_min, up_min + t, down_min - t)

        return (x0 - x1) * (y0 - y1)

    ans = 10**18
    for t in inflections:
        ans = min(ans, get_val(t))

    return ans


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


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted