首页 > 代码库 > HDU 3400 Line belt （三分嵌套）

HDU 3400 Line belt （三分嵌套）

2024-08-04 04:27:19   218人阅读

题目链接

Line belt

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


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
10 0 0 100100 0 100 1002 2 1
 

 

Sample Output
136.60
 

 

Author
lxhgww&&momodi
 

题意：

给出两条传送带的起点到末端的坐标，其中ab为p的速度，cd为q的速度 其他地方为r的速度

求a到d点的最短时间。

分析：

首先要看出来这是一个凹型的函数，

时间最短的路径必定是至多3条直线段构成的，一条在AB上，一条在CD上，一条架在两条线段之间。

所有利用两次三分，第一个三分ab段的一点，第二个三分知道ab一点后的cd段的接点。

刚开始没用do while错了两次，因为如果给的很接近的话，上来的t1没有赋值。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #define LL __int64 8 const int maxn = 1e2 + 10; 9 const double eps = 1e-8;10 using namespace std;11 double p, q, r;12 struct node13 {14     double x, y;15 }a, b, c, d;16 17 double dis(node a, node b)18 {19     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));20 }21 22 double solve2(node t)23 {24     double d1, d2;25     node le = c;26     node ri = d;27     node mid, midmid;28     do29     {30         mid.x = (le.x+ri.x)/2.0;31         mid.y = (le.y+ri.y)/2.0;32         midmid.x = (mid.x+ri.x)/2.0;33         midmid.y = (mid.y+ri.y)/2.0;34         d1 = dis(t, mid)/r + dis(mid, d)/q;35         d2 = dis(t, midmid)/r + dis(midmid, d)/q;36         if(d1 > d2)37         le = mid;38         else ri = midmid;39     }while(dis(le, ri)>=eps);40     return d1;41 }42 43 double solve1()44 {45     double d1, d2;46     node le = a;47     node ri = b;48     node mid, midmid;49     do50     {51         mid.x = (le.x+ri.x)/2.0;52         mid.y = (le.y+ri.y)/2.0;53         midmid.x = (mid.x+ri.x)/2.0;54         midmid.y = (mid.y+ri.y)/2.0;55         d1 = dis(a, mid)/p + solve2(mid);56         d2 = dis(a, midmid)/p + solve2(midmid);57         if(d1 > d2)58         le = mid;59         else ri = midmid;60     }while(dis(le, ri)>=eps);61     return d1;62 }63 64 int main()65 {66     int t;67     scanf("%d", &t);68     while(t--)69     {70         scanf("%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y);71         scanf("%lf%lf%lf%lf", &c.x, &c.y, &d.x, &d.y);72         scanf("%lf%lf%lf", &p, &q, &r);73         printf("%.2lf\n", solve1());74     }75     return 0;76 }

 

HDU 3400 Line belt （三分嵌套）


联系
我们