问题 5792 --兔兔找三角形5792: 兔兔找三角形
时间限制: 1 Sec 内存限制: 128 MB
提交: 69 解决: 36
[提交][状态][命题人:]题目描述
在一个平面直角坐标系中画一个左下角坐标为 (0,0)并且右上角坐标为 (w,h) 的一个矩形。保证矩形的四条边都与坐标轴平行。
在直线y=0 上有k1 个点 (x1,0),(x2,0),⋯,(xk1,0),保证x1<x2<⋯<xk1。
在直线y=h 上有k2 个点 (x1,h),(x2,h),⋯,(xk2,h),保证 x1<x2<⋯<xk2。
在直线 x=0 上有k3 个点 (0,y1),(0,y2),⋯,(0,yk3),保证y1<y2<⋯<yk3。
在直线x=w 上有k4 个点 (w,y1),(w,y2),⋯,(w,yk4),保证y1<y2<⋯<yk4。
兔兔需要找到一条直线上的任意两点和另一条直线上的任意一点,使得构成的三角形面积最大。数据保证每条直线上至少有 2 个点。
输出最大三角形面积的2倍,即计算三角形面积不需要除以2。
输入
第一行一个整数 t(1≤t≤10000),代表数据组数。
每组数据第一行两个整数w,h(3≤w,h≤1000000)。
接下来四行,分别为y=0、y=h、x=0和x=w边上的点。对于每一行,第一个整数是 ki(2≤ki≤100000),接下来ki个整数 ,代表每个点的坐标,如题目描述。数据保证每个测试点的k值的总和不超过200000。
输出
每组数据中能组成的最大三角形的面积的2倍。数据保证最后的结果是整数。
提示
在第1个测试样例中点的坐标如下:
•(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),其面积为25/2。因此答案为25。
来源
[提交][状态]