Problem Description
The head technical person, Joey, at ACM (Association for Cyberspace Management)has just received a weird cable-like device – supposedly invented by programmers during a competition – for inspection.
The device may be viewed as a straight bi-directional cable, which can be used for transmitting arbitrary number of data packages simultaneously. The speed with which each package is sent will be pre-determined by the device and furthermore may vary within a certain range; however it will remain constant throughout each package’s entire transmission process. The time it takes for a single data package with speed V to arrive at the opposite end of the cable is thus L/V, where L is the length of the cable.
In addition, the user may sometimes send a fixed-speed “detector” package,
which is capable of reporting the number of data packages alongside itself at any time.
Finding this device highly amusing, Joey decides to perform an experiment on the odd “cable”. He has scheduled N packages to be sent from the left side and another M to be sent from the other side of the cable; also, he has calculated the possible speed range for each data package. With this information in hand, Joey wants to estimate the effectiveness of a detector he will send. For a detector that departs at a certain time, its effectiveness can be represented as a real number in the range [0..1], which is simply the ratio of the time during which the detector has a chance of reporting all N + M packages (explained below) to the total time.
If Joey sends the detector at an arbitrary time in [S, T] with speed V from the left side of the cable, what is the average effectiveness he can achieve?
Note: For a detector to have a chance of reporting all N + M packages at time T0, the device must be able to schedule all data packages with such speeds so that all can share the same position with the detector at time T0.
Input
There are multiple test cases in the input file.
Each test case starts with one integer, L ( 1 ≤ L ≤ 106), the length of the cable.
The next line contains one integer, N, the number of packages Joey will send from the
left side, followed by N lines, the ith line with three real numbers, MinVi, MaxVi, and Leavei(1≤MinVi≤MaxVi), which are the minimum speed, maximum speed, and
departure time for package i , respectively. Another (M + 1) lines follow, describing the
packages departing from the right side. The last line of the input contains three real numbers, S, T and V (T - S ≥ 1), whose meanings are described above.
The total number of packages Joey sent will be in the interval [1,5000]. It is
guaranteed that the speed of any data packet, including that of the detector, will be no less than 0.01; also, all real numbers in the input will be given with at most two digits after the decimal point, and will belong to the interval: [0 , 106].
Two successive test cases are separated by a blank line. A case with L = 0
indicates the end of the input file, and should not be processed by your program.
Output
Please print the average effectiveness of the detector’s trip, with precision up to 0.00001.
Sample Input
5
1
5.00 10.00 2.00
2
10.05 11.50 0.05
1.68 2.00 0.01
3.00 4.00 1000
5
1
1.25 2.50 1.0
0
1.00 5.00 2.50
0
Sample Output
Case #1: 0.00000
Case #2: 0.25000
