F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

How Long Do You Have to Draw

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 568    Accepted Submission(s): 254


Problem Description
There are two horizontal lines on the XoY plane. One is y1 = a, the other is y2 = b(a < b). On line y1, there are N points from left to right, the x-coordinate of which are x = c1, c2, ... , cN (c1 < c2 < ... < cN) respectively. And there are also M points on line y2 from left to right. The x-coordinate of the M points are x = d1, d2, ... dM (d1 < d2 < ... < dM) respectively.
Now you can draw segments between the points on y1 and y2 by some segments. Each segment should exactly connect one point on y1 with one point on y2.
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 <= 104), which is the position of y1 and y2.
The second line has two numbers N and M (1 <= N, M <= 105), which is the number of points on y1 and y2.
The third line has N numbers c1, c2, .... , cN(0 <= ci < ci+1 <= 106), which is the x-coordinate of the N points on line y1.
The fourth line has M numbers d1, d2, ... , dM(0 <= di < di+1 <= 106), which is the x-coordinate of the M points on line y2.
 

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.
 

Sample Input
1 0 1 2 3 1 3 0 2 4
 

Sample Output
Case #1: 5.66
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-05-05 12:21:37, Gzip enabled