编程介的小学生
2019-03-28 16:59
采纳率: 92.5%
浏览 166

线路的优化算法问题,已经知道图上的顶点,用C语言程序设计来计算

Problem Description
“Help! Help!”

While walking in the park, you suddenly hear someone shouting for help. You immediately realize that a person has fallen into the lake. As a brave man, you decide to save him.

You are really familiar with the terrain of the park. The park can be regarded as a 2D plane. And the lake is a convex polygon. At current, you are on (Xo, Yo), and the person is on (Xp, Yp). You also know that you can run Vr per second on the land, or swim Vs per second in the lake. Notice that you are allowed to run along the edge of the lake.

You are not good at swimming. You cannot stay in the lake longer than Ts second. And carrying another person will cut down your swimming speed by half.

Can you save the poor guy? What is the minimum time for you to reach him, and carry him back to the border of the lake?

Input
There are several test cases in the input.

The first line contains an integer T (1 <= T <= 20) -- the number of test cases.

For each case:

The first line contains three real numbers Ts, Vr, Vs. 0 < Ts < 108, 0 < Vs < Vr < 108.

The second line contains two real numbers Xo, Yo, indicate the position (Xo, Yo) of you at current.

The third line contains two real numbers Xp, Yp, indicate the position (Xp, Yp) of the person you are going to save.

The forth line contains only one integer N -- the number of vertices of the lake. 3 <= N <= 50000.

The follow N lines, each line contains two real numbers x, y, indicating one of the vertex (x, y) of the lake. The vertices of lake are listed in either clockwise or counter-clockwise order.

Each coordinate in the input does not exceed 106 by its absolute value. Your position is on the land and the person’s is in the lake.

Output
For each test case, output the minimum time(in seconds) to save the poor person, rounded to two digits after the decimal point. If you cannot save he, output “-1” instead.

Sample Input
2
100 2 1
0 10
0 0
3
-1 1
1 1
0 -1
1 2 1
0 10
0 0
3
-1 1
1 1
0 -1

Sample Output
6.39
-1

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

相关推荐 更多相似问题