How Long Do You Have to Draw
TimeLimit:1000MS MemoryLimit:32768KB
64-bit integer IO format:%I64d
Problem Description
There are two horizontal lines on the
XoY plane. One is y
1 = a, the other is y
2 = b(a < b). On line y
1, there are N points from left to right, the x-coordinate of which are x = c
1, c
2, ... , c
N (c
1 < c
2 < ... < c
N) respectively. And there are also M points on line y
2 from left to right. The x-coordinate of the M points are x = d
1, d
2, ... d
M (d
1 < d
2 < ... < d
M) respectively.
Now you can draw segments between the points on y
1 and y
2 by some segments. Each segment should exactly connect one point on y
1 with one point on y
2.
The segments cannot cross with each other. By doing so, these segments, along with y1 and y2, can form some triangles, which have positive areas and have no segments inside them.
The problem is, to get as much triangles as possible, what is the minimum sum of the length of these segments you draw?
Input
The first line has a number T (T <= 20) , indicating the number of test cases.
For each test case, first line has two numbers a and b (0 <= a, b <= 10
4), which is the position of y
1 and y
2.
The second line has two numbers N and M (1 <= N, M <= 10
5), which is the number of points on y
1 and y
2.
The third line has N numbers c
1, c
2, .... , c
N(0 <= c
i < c
i+1 <= 10
6), which is the x-coordinate of the N points on line y
1.
The fourth line has M numbers d
1, d
2, ... , d
M(0 <= d
i < d
i+1 <= 10
6), which is the x-coordinate of the M points on line y
2.
Output
For test case X, output "Case #X: " first, then output one number, rounded to 0.01, as the minimum total length of the segments you draw.