Line belt |
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
Total Submission(s): 85 Accepted Submission(s): 47 |
Problem Description
In a two-dimensional plane there are two line belts, there are two segments AB and CD, lxhgww's speed on AB is P and on CD is Q, he can move with the speed R on other area on the plane.
How long must he take to travel from A to D? |
Input
The first line is the case number T.
For each case, there are three lines. The first line, four integers, the coordinates of A and B: Ax Ay Bx By. The second line , four integers, the coordinates of C and D:Cx Cy Dx Dy. The third line, three integers, P Q R. 0<= Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000 1<=P,Q,R<=10 |
Output
The minimum time to travel from A to D, round to two decimals.
|
Sample Input
1 0 0 0 100 100 0 100 100 2 2 1 |
Sample Output
136.60
三分搜索:
如图所示必定在AB CD上存在XY 使得A---D 用时间最短。用三分法针对AB间的某个点找出在CD段上最小的点, 嵌套循环找出最小的时间。有关时间函数在AB段和在CD段均为凸函数,所以可以用三分法。 #include <iostream> |