hdu 3400 Line belt(多重三分)

hdu 3400 Line belt(多重三分)

题目：​​belt​​

​​Submit​​​ ​​Status​​

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上的a向量，CD上的c向量，其他区域的b向量。三者满足这样的关系：(1)|a+b+c|=|AD|  (2)|a|/p+|b|/r+|c|/q=min_time.  (3) 0<=|a|<=|AB|   (4)0<=|c|<=|CD|   (5) |b|=|AD|-|a+c|  因为是极值问题自然想到三分，可是向量怎么用长度表示？不能，只有用二维坐标，把所有的位置信息存在点里，计算距离，第三个点的位置推导全部用坐标来解决。

pt,qt都是两条线段上运动的点，pt,qt的坐标可以通过线段长度之比推导出来。最后的结果确定：每定一个pt点就对qt三分，找A--pt,pt--qt,qt--D的长度之和，pt用一次三分，qt在pt的基础上再用三分，即pt在AB上动一下，qt在CD上转悠一圈。

#include #include #include using namespace std;const double eps=1e-7,Min=1e-9;struct node{ double x,y;}a,b,c,d,pt,qt;double lab,lcd,p,q,r;double dist(node q1,node q2){ return sqrt(eps+(q1.x-q2.x)*(q1.x-q2.x)+(q1.y-q2.y)*(q1.y-q2.y)); //eps不能缺}void calpt(double ra){ pt.x=a.x+ra/lab*(b.x-a.x); pt.y=a.y+ra/lab*(b.y-a.y);}void calqt(double ra){ qt.x=d.x+ra/lcd*(c.x-d.x); qt.y=d.y+ra/lcd*(c.y-d.y);}double cal(double ra){ calpt(ra); double low=0,high=lcd,mid1,mid2,ans=dist(pt,a)/p,ans2,ans3; while(high-low>Min){ mid1=low+(high-low)/3; mid2=high-(high-low)/3; calqt(mid1); ans2=dist(qt,pt)/r+dist(qt,d)/q; calqt(mid2); ans3=dist(qt,pt)/r+dist(qt,d)/q; if(ans2>t; while(t--){ double ax,ay,bx,by,cx,cy,dx,dy; scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by); a.x=ax; a.y=ay; b.x=bx; b.y=by; scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy); c.x=cx; c.y=cy; d.x=dx; d.y=dy; scanf("%lf%lf%lf",&p,&q,&r); lab=dist(a,b),lcd=dist(c,d); double low=0,high=lab,mid1,mid2; while(high-low>Min){ mid1=low+(high-low)/3; mid2=high-(high-low)/3; if(cal(mid1)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。