Triangles on a Rectangle

题意翻译

## 题目描述 在一个平面直角坐标系中画一个左下角坐标为 $(0,0)$ 并且右上角坐标为 $(w,h)$ 的一个矩形。保证矩形的四条边都与坐标轴平行。 在直线 $y=0$ 上有 $k_1$ 个点 $(x_1,0),(x_2,0),\cdots,(x_{k_1},0)$，保证 $x_1<x_2<\cdots<x_{k_1}$。 在直线 $y=h$ 上有 $k_2$ 个点 $(x_1,h),(x_2,h),\cdots,(x_{k_2},h)$，保证 $x_1<x_2<\cdots<x_{k_2}$。 在直线 $x=0$ 上有 $k_3$ 个点 $(0,y_1),(0,y_2),\cdots,(0,y_{k_3})$，保证 $y_1<y_2<\cdots<y_{k_3}$。 在直线 $x=w$ 上有 $k_4$ 个点 $(w,y_1),(w,y_2),\cdots,(w,y_{k_4})$，保证 $y_1<y_2<\cdots<y_{k_4}$。 你需要找到一条直线上的任意两点和另一条直线上的任意一点，使得构成的三角形面积最大。数据保证每条直线上至少有 $2$ 个点。 输出最大三角形面积的 $2$ 倍，也就是计算三角形面积不需要除以 $2$。 ## 输入格式 第一行一个整数 $t(1\le t\le 10^4)$，代表数据组数。 对于每一组数据： 第一行两个整数 $w,h(3\le w,h\le 10^6)$。 接下来四行，对于第 $i$ 行，第一个整数是 $k_i(2\le k_i\le 10^5)$，接下来 $k_i$ 个整数 ，代表每个点的坐标，如题目描述。数据保证每个测试点的 $k$ 值的总和不超过 $2\times 10^5$。 ## 输出格式 输出每一组数据的能组成的最大三角形的面积的$2$倍。数据保证最后的结果是整数。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

25
42
35

说明

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) $ .