One of the biggest problem in cities is traffic jams. One reason for forming traffic jams is the intersections, where all the cars try to cross the road as soon as possible.
To reduce traffic jams, the mayor of Incredibly Congested Poor City (ICPC) decided to install a traffic light at a crossroad where two roads intersect. At each moment the traffic light is green for cars on one road, and red for cars on the other road. A car can pass the intersection only when the light is green for its road. At the moment of traffic light switching, cars on both roads can pass. (Incredible!)
The traffic light is arranged as follows: At time 0, the light is green for cars on the first road, and red for cars on the second road. Next, after g seconds, it switches to red for cars on the first road and green for cars on the second road. Then, after r seconds, it switches back to green for the first road, etc.
Thus, the light is green for the first road at the times [k(r+g), k(r+g)+g] for non-negative integer k, and green for the second road at the times [k(r+g)+g, (k+1)(r+g)]. Switching occurs at the times k(r+g) and k(r+g)+g. We neglect the time of a car to pass the intersection. When a car arrives the intersection, if the traffic light is green for its road, this car can pass the intersection immediately. If the difference between the arriving time of the car and the switching time of traffic light is no more than 10-5, this car can also pass the intersection immediately. Otherwise, the car stops and waits until the next green light for its road.
In accordance with the technical documentation, the period of the traffic light must be equal to x. In other words, we must have r+g=x. Subject to this condition, any non-negative real numbers can be chosen to be the values of r and g.
On each of the roads there are several cars that travel in the direction of the intersection. The cars do not overtake each other. Each time a car catches a slower one, it reduces the speed and immediately follows the slower car with an appropriate speed. The size of the cars and the time of changing speed can be neglected. When a car arrives the intersection, if it can pass the intersection (according to the rules above), it will pass the intersection immediately.
At time 0, there are n cars on the first road. The i-th car is located at a distance a_i meters from the intersection, and moving toward the intersection with velocity v_i m/s. Similarly, there are m cars on the second road. The j-th car is located at a distance b_j meters from the intersection, and moving toward the intersection with velocity w_j m/s.
To reduce the congestion in ICPC, it is necessary to choose g and r to minimize the maximum number of cars waiting at the intersection at the same time. Please help the mayor to choose the optimal g and r.
Warn: 本題有 specialjudge
The first line of the input file contains an integer T, indicating the number of test cases.
For each test case, the first line gives a real number x. The second line contains the integer n, the number of cars on the first road. Each of the next n lines gives the description of a car on the first road. The i-th line consists of two real numbers, a_i and v_i, the distance from the car to the intersection and the velocity, respectively. The next line contains the integer m, the number of cars on the second road. The following m lines contains the descriptions of the cars, b_j and w_j, in the same format.
The input guarantees that no two cars are initially at the same point, and both lists of the cars are given in increasing order of the distance.
0<= n,m<= 100000, 1<= n+m<= 100000, 1<= x, a_i, v_i, b_j, w_j<= 10^4. The real numbers are given with no more than three digits after the decimal point.
For each test case output one line, containing an integer k, and two real numbers g and r, separated by a white space.
The output integer k should be minimized such that when applying outputted g and r to the traffic light
there would be no more than k cars waiting at the intersection at the same time.
The output of g and r should be accurate to at least 6 digits after the decimal point.
If there are multiple optimal solutions, you may output any one of them.
2 2.0 1 1.0 1.0 2 1.0 1.0 2.0 2.0 4.0 3 2.0 1.0 4.0 5.0 5.0 20.0 3 1.0 1.0 5.0 1.0 7.0 1.0
0 1.000000 1.000000 1 2.000000 2.000000
Migrated from old NTUJ.
St. Petersburg Olympiad team programming 2011
| No. | Testdata Range | Score |
|---|