← 返回题目列表

Codeforces · 1620/B

B. 矩形上的三角形

中文机器翻译题面 查看原题

在平面上绘制一个矩形,其对角位于 $$$(0, 0)$$$ 和 $$$(w, h)$$$ 且边平行于轴。

给你一个格点列表,每个点都位于矩形的一边,但不在其角上。此外,矩形的每条边上至少有两个点。

您的任务是选择三个点,以便:

- 其中两个恰好属于矩形的同一边;
- 由它们形成的三角形面积是最大可能的。

打印该三角形的两倍面积。可以证明,由格点构成的任意三角形的两倍面积始终是整数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$w$$$ 和 $$$h$$$ ($$$3 \le w, h \le 10^6$$$) - 矩形角的坐标。

接下来的两行包含两个水平边上的点的描述。首先,一个整数 $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) — 点数。然后,$$$k$$$ 整数 $$$x_1 < x_2 < \dots < x_k$$$ ($$$0 < x_i < w$$$) - 按升序排列的点的 $$$x$$$ 坐标。第一行的 $$$y$$$ 坐标是 $$$0$$$,第二行的 $$$h$$$ 坐标是 $$$h$$$。

接下来的两行包含两个垂直边上的点的描述。首先,一个整数 $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) — 点数。然后,$$$k$$$ 整数 $$$y_1 < y_2 < \dots < y_k$$$ ($$$0 < y_i < h$$$) — 按升序排列的点的 $$$y$$$ 坐标。第一行的 $$$x$$$ 坐标是 $$$0$$$,第二行的 $$$w$$$ 坐标是 $$$w$$$。

所有测试用例中所有边的点数总数不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 由这三个点形成的三角形的最大面积的两倍,其中恰好有两个点属于同一边。

示例

输入 #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

注意

示例第一个测试用例中的要点:

- $$$(1, 0)$$$, $$$(2, 0)$$$;
- $$$(2, 8)$$$, $$$(3, 8)$$$, $$$(4, 8)$$$;
- $$$(0, 1)$$$, $$$(0, 4)$$$, $$$(0, 6)$$$;
- $$$(5, 4)$$$, $$$(5, 5)$$$.

最大的三角形由点 $$$(0, 1)$$$、$$$(0, 6)$$$ 和 $$$(5, 4)$$$ 形成 - 其面积为 $$$\frac{25}{2}$$$。因此,加倍的面积为 $$$25$$$。位于同一侧的两个点是:$$$(0, 1)$$$ 和 $$$(0, 6)$$$。