CF1620B 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

第一行一个整数 $t$（$1 \leq t \leq 10^4$），代表数据组数。 对于每一组数据： 第一行两个整数 $w,h$（$3 \leq w,h \leq 10^6$）。 接下来的两行包含两个水平线上的点的描述。每行首先是一个整数 $k$（$2 \leq k \leq 2 \cdot 10^5$）表示点的数量。然后是 $k$ 个整数 $x_1 < x_2 < \cdots < x_k$（$0 < x_i < w$）表示按升序排列的点的 $x$ 坐标。第一条水平线的 $y$ 坐标为 $0$，第二条水平线的 $y$ 坐标为 $h$。 接下来的两行包含两个竖直线上的点的描述。每行首先是一个整数 $k$（$2 \leq k \leq 2 \cdot 10^5$）表示点的数量。然后是 $k$ 个整数 $y_1 < y_2 < \cdots < y_k$（$0 < y_i < h$）表示按升序排列的点的 $y$ 坐标。第一条竖直线的 $x$ 坐标为 $0$，第二条竖直线的 $x$ 坐标为 $w$。 所有测试用例中所有边上的点总数不超过 $2 \cdot 10^5$。

输出每一组数据的能组成的最大三角形的面积的$2$倍。数据保证最后的结果是整数。

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