Triangles on a Rectangle (Codeforces 1620B)
Tags: Greedy, geometry

A rectangle with its opposite corners in $$$(0, 0)$$$ and $$$(w, h)$$$ and sides parallel to the axes is drawn on a plane.You are given a list of lattice points such that each point lies on a side of a rectangle but not in its corner. Also, there are at least two points on every side of a rectangle.Your task is to choose three points in such a way that:   exactly two of them belong to the same side of a rectangle;  the area of a triangle formed by them is maximum possible. Print the doubled area of this triangle. It can be shown that the doubled area of any triangle formed by lattice points is always an integer.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.The first line of each testcase contains two integers $$$w$$$ and $$$h$$$ ($$$3 \le w, h \le 10^6$$$) — the coordinates of the corner of a rectangle.The next two lines contain the description of the points on two horizontal sides. First, an integer $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) — the number of points. Then, $$$k$$$ integers $$$x_1 < x_2 < \dots < x_k$$$ ($$$0 < x_i < w$$$) — the $$$x$$$ coordinates of the points in the ascending order. The $$$y$$$ coordinate for the first line is $$$0$$$ and for the second line is $$$h$$$.The next two lines contain the description of the points on two vertical sides. First, an integer $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) — the number of points. Then, $$$k$$$ integers $$$y_1 < y_2 < \dots < y_k$$$ ($$$0 < y_i < h$$$) — the $$$y$$$ coordinates of the points in the ascending order. The $$$x$$$ coordinate for the first line is $$$0$$$ and for the second line is $$$w$$$.The total number of points on all sides in all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each testcase print a single integer — the doubled maximum area of a triangle formed by such three points that exactly two of them belong to the same side.

Note: The points in the first testcase of the example:   $$$(1, 0)$$$, $$$(2, 0)$$$;  $$$(2, 8)$$$, $$$(3, 8)$$$, $$$(4, 8)$$$;  $$$(0, 1)$$$, $$$(0, 4)$$$, $$$(0, 6)$$$;  $$$(5, 4)$$$, $$$(5, 5)$$$. The largest triangle is formed by points $$$(0, 1)$$$, $$$(0, 6)$$$ and $$$(5, 4)$$$ — its area is $$$\frac{25}{2}$$$. Thus, the doubled area is $$$25$$$. Two points that are on the same side are: $$$(0, 1)$$$ and $$$(0, 6)$$$.

Sample Inputs:
3
5 8
2 1 2
3 2 3 4
3 1 4 6
2 4 5
10 7
2 3 9
2 1 7
3 1 3 4
3 4 5 6
11 5
3 1 6 8
3 3 6 8
3 1 3 4
2 2 4

Sample Outputs:
25
42
35

Solution (Python):
def main():
    t = int(input())
    allans = []
    for _ in range(t):
        (w, h) = readIntArr()
        x_with_y0 = readIntArr()[1:]
        x_with_yh = readIntArr()[1:]
        y_with_x0 = readIntArr()[1:]
        y_with_xw = readIntArr()[1:]
        ans = max(h * max(x_with_y0[-1] - x_with_y0[0], x_with_yh[-1] - x_with_yh[0]), w * max(y_with_x0[-1] - y_with_x0[0], y_with_xw[-1] - y_with_xw[0]))
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ansArr):
    print('! {}'.format(' '.join([str(x) for x in ansArr])))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
from sys import stdin, stdout
input = stdin.readline
from math import sqrt, ceil

def print(*args, end='\n', sep=' ') -> None:
    stdout.write(sep.join(map(str, args)) + end)
for _ in range(int(input())):
    (w, h) = map(int, input().split())
    ax = list(map(int, input().split()))
    bx = list(map(int, input().split()))
    ay = list(map(int, input().split()))
    by = list(map(int, input().split()))
    print(max((ax[-1] - ax[1]) * h, (bx[-1] - bx[1]) * h, (ay[-1] - ay[1]) * w, (by[-1] - by[1]) * w))

Solution (Python):
t = int(input())
ans = []
for _ in range(t):
    (w, h) = map(int, input().split())
    h0 = list(map(int, input().split()))
    hh = list(map(int, input().split()))
    v0 = list(map(int, input().split()))
    vw = list(map(int, input().split()))
    ans.append(max(h * max(h0[-1] - h0[1], hh[-1] - hh[1]), w * max(v0[-1] - v0[1], vw[-1] - vw[1])))
for a in ans:
    print(a)