題意： 有兩條線段，在其中一條線段上移動的速度為 v1,在另一條線上速度為v2, 在其他地方移動速度為 r,問從其中一條線段的一個端點移動到另一個線段

?????????? 的一個端點的最少時間。

分析： 在其中一條線段上三分離開的點，枚舉之后再進行一次三分求最優解，關鍵在于看出函數是凸性的。

#include<stdio.h> #include<string.h> #include<math.h> const double eps=1e-6; struct node {double x,y; }; double dis(node a,node b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double v1,v2,R;double tcal(node a,node c,node d) {node l,r;node mid,midmid;double l1,l2;l=c;r=d;while(dis(l,r)>=eps){mid.x=(l.x+r.x)/2;mid.y=(l.y+r.y)/2;midmid.x=(mid.x+r.x)/2;midmid.y=(mid.y+r.y)/2;l1=dis(a,mid)/R+dis(mid,d)/v2;l2=dis(a,midmid)/R+dis(midmid,d)/v2;if(l1>l2)l=mid;else r=midmid;}return l1; }double cal(node a,node b,node c,node d) {node l,r;node mid,midmid;double l1,l2;l=a;r=b;do{mid.x=(l.x+r.x)/2;mid.y=(l.y+r.y)/2;midmid.x=(mid.x+r.x)/2;midmid.y=(mid.y+r.y)/2;l1=dis(a,mid)/v1+tcal(mid,c,d);l2=dis(a,midmid)/v1+tcal(midmid,c,d);if(l1>l2)l=mid;else r=midmid;}while(dis(r,l)>=eps);return l1;}int main() {node a,b,c,d;int t;scanf("%d",&t);while(t--){scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);scanf("%lf%lf%lf",&v1,&v2,&R);printf("%.2lf\n",cal(a,b,c,d));}return 0; }

?

轉載于:https://www.cnblogs.com/dream-wind/archive/2012/09/05/2672302.html

總結

以上是生活随笔為你收集整理的HDU 3400 Line belt【三分法】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。